Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-geometry]

Discrete geometry includes the study of covering, illumination, packing, convex bodies, convex polytopes, and other metric geometry.

0
votes
0answers
16 views

Variation On Orchard Problems (VOOP?)

You are standing at the origin in the Cartesian Plane. At each lattice point, there is a tree, a circle with radius 0.1. How far away are the centers of the trees that cut off the last vestiges of ...
0
votes
0answers
40 views

How to calculate volume of an intersection between a hyperrectangle and an N-dimensional ball in multiple dimensions

First of all, this question is technically an extension of this question: https://stackoverflow.com/questions/54846852/caseless-way-of-calculating-volume-of-an-intersection-between-an-array-and-a-squ ...
2
votes
1answer
30 views

Arrange points such that translates of orthants separate subsets of them

Is it possible to arrange $n$ distinct points $A = \{x_1, \ldots, x_n\} \subseteq \mathbb R^k$ so that every subset $B \subseteq A$ could be written as $$ (y_B + \mathbb R_{\ge 0}^k) \cap A $$ for ...
1
vote
1answer
45 views

Projective Transformation for two distinct vertices and a linear objective function

I am trying to understand how to prove the following, which seems to be a quite useful insight in terms of linear optimization. Unfortunately, I have a hard time with projective geometry. I'd greatly ...
0
votes
1answer
19 views

Voronoi Diagram point set input

Is it possible to make a Voronoi diagram out of a non-simple convex hull set of points or a non-simple polygon? I have a set of points that make up a convex hull, but within the set of points, there ...
0
votes
0answers
25 views

Counting approximations of a flat shape by subsets of square tiling

A closed topological disk $K$ is approximated by the maximal subset of faces of the square tiling that are contained in the interior of $K$. As $K$ is translated and/or rotated in the plane, the ...
4
votes
0answers
46 views

Does there always exist a Chebyshev center of three constant weight points in $\mathbb F_2^n$ which is equidistant?

Given three distinct points $x_1,x_2,x_3$ in $\mathbb F_2^n$ (endowed with the Hamming metric $d(\cdot,\cdot)$) with the same (but arbitrary) Hamming weight, the Chebyshev radius of them is defined as ...
0
votes
0answers
34 views

Discrete Geometry Pre-requisites

I have started studying Lectures on Discrete Geometry by Jiri Matousek, chapter 1 was fine for me I am midway chapter 2 but I am not understanding most of things after this. Are there any other books ...
2
votes
1answer
34 views

Number of facets of the Birkhoff polytopes $B(n)$.

The wikipedia's page for Birkhoff polytope states that the polytope has $n^2$ facets, determined by the inequalities $x_{ij} \geq 0$, for $1 \leq i,j \leq n$. I've tried different things but can't see ...
0
votes
1answer
18 views

Given two polytopes $P$ and $Q$, show that $(P^* \times Q^*)^* = P \oplus Q $

Using definitions, I got so far as to express $(P^* \times Q^*)^*$ in the following form: $$(P^* \times Q^*)^* = \left\{\,\begin{pmatrix} z^* \\ w^* \end{pmatrix} \in \mathbb{R}^{d+e} \,\middle|\,...
0
votes
1answer
67 views

Finding vertices of a polytope with a given set of inequalities.

I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, and a set of bounds for the coordinates: $v_k\in[0,a_k],\ 1\le k\le n$, where $a_1\ge a_2\ge \cdots\ge a_n\ge 0$. My question is: ...
0
votes
1answer
30 views

Show that each edge of the cyclic polytope $C_4(6)$ is contained in either three or four facets, and either three or four 2-faces.

Note: here $C_4(6)$ is the notation for the cyclic polytope of dimension 4 and of 6 vertices. By the 2-neighbourly property of $C_4(6)$ and the Dehn-Sommerville equations, I've determined that the ...
0
votes
0answers
33 views

Proof of Helly's Theorem

In the proof it says the case for $n=d+1$ is clear. What does it mean by that and here $n$ is the number of sets. Where as in case for $n=d+2$ is understandable for $d=2$ where it proceeds by ...
2
votes
0answers
71 views

How to check the dimension of a given set in $\mathbb R^n$?

So, after an extensive search I found no answer for this, although it might be because I don't have the knowledge to ask the right question. Imagine that you are given a finite set of points $S$ in $\...
1
vote
0answers
12 views

Number of odd contiguous sets under permutation

Part of a problem that I'm trying to solve involves the following situation: let $S = \{t_1,...,t_n\}$ be a set of n points in a line. Let $W = \{t_{i_1},...,t_{i_k}\}$ be a k-subset of S, such that ...
0
votes
0answers
55 views

Gale's evenness condition applied to cyclic polytopes and simplices

Please give your comment on the following problem. In our class we use the following definitions and the following version of the Gale's evenness condition. My analysis of part a is that, the graph $...
4
votes
1answer
55 views

Definitions of pyramid (eg, tetrahedron as “$1$-fold $3$-pyramid” vs “$3$-fold pyramid”)

My lecture note and my textbook offer slightly different definitions of pyramid. Here's the one from the lecture: And here's the one from the textbook: I just want to make sure I interpret the two ...
0
votes
3answers
25 views

3-polytope with 9 vertices and 8 facets

My guess is that this is a 3-polytope, since the existence of the two facets {357} and {048} rules out the possibility of dimensionality 2 and 4. How can I go about sketching it?
6
votes
1answer
105 views

A formula for the number of possible combinations of a $i\times j$ rectangle in a $m\times n$ grid such that they don't overlap?

Suppose I have a grid of size $m\times n$ and a rectangle of length $i\times j$ where $i$ and $j$ are integers as shown here for where $m = 7$, $n = 5$, $i = 2$, $j = 3$:  Does there exist a ...
1
vote
1answer
29 views

Permutahedron of three vectors (1,1,0,0), (−1,1,0,0), (−1,−1,0,0).

I'm getting stuck on parts b, c, and d. Since visualizing the polytope is not possible, I think the way to find the facets and edges of P is to determine which combinations of points form facets and ...
5
votes
2answers
43 views

How many uniform polytopes are there in higher dimensions?

I am not really interested in the exact numbers, but more in the richness of the class of uniform (convex) polytopes in higher dimensions. Wikipedia contains the followin statement: In five and ...
3
votes
3answers
167 views

Product of two polytopes is a polytope

Please have a look at my attempt for this problem. Let $x = \begin{pmatrix} x_1\\ x_2 \\ \end{pmatrix}, x_1 \in P_1, x_2 \in P_2$. I want to show that $x \in conv\{P_1 \times P_2\}$, i.e. $x$ can be ...
0
votes
1answer
17 views

Definition of centrally symmetric polytopes

I'm doing this exercise and have trouble with the definition of centrally symmetric polytopes. I understand what it means, but it just doesn't look like a workable definition in solving this problem. ...
1
vote
1answer
54 views

Prove that a cone C is full-dimensional if and only if its dual cone $C^*$ is pointed.

A cone with apex $0$ is said to be pointed if it does not contain any non-trivial subspace. Let C be a closed convex cone with apex $0$. Show that $C$ is full-dimensional if and only if its dual cone $...
1
vote
0answers
24 views

Is there proof of equation $P = L - I + 1$ in the $2D$ space from the computational geometry?

QUESTION: Does exist a proof of statement $ P = L - I + 1$, where $P$ stands for number of polygons, $L$ for number of line segments, $I$ for number of intersection points, in any arrangement made ...
0
votes
0answers
28 views

Is the following set Convex (Discrete sense)?

Let us consider the set below. Elements of the set contains finite number of m-tuple of non-negative integers. $$S(n,m)=\{R=(R_1, R_2,\dots,R_m\} \in N^m | \sum_{i=1}^{m} R_i=n-m, N=\{0,1,\dots,n-m\}...
1
vote
0answers
22 views

Comparing discretized manifolds

being quite unsure which keywords to search with, I have a quick question on comparing discrete manifolds: Let's say we have have two smooth $2$-manifolds $M1$ and $M2$ in $\mathbb R^3$. Of these ...
6
votes
2answers
295 views

Rosenfeld's $7 \times 7$ square puzzle

A $7 \times 7$ square puzzle may be described as following. Start with a $7 \times 7$ square divided into $7 \cdot 7$ unit squares. First select a unit square and mark it. And then, in each ...
7
votes
0answers
82 views

Determining finitude or infinitude from a simple geometric construction

Playing with a pencil on a checkered sheet I encountered this construction: 1) take a point $A$ on the grid and a point $B$ that is distant from $A$ $n=2,3,4...$ horizontal steps and $1$ vertical ...
2
votes
1answer
31 views

Packing densities in grid world

Suppose there is a 25x50 grid world with 1250 grid cells. Suppose some of them are colored black (full) and some are white (empty). We are interested in quantifying the packing of this grid world. If ...
1
vote
0answers
79 views

Proof of Caratheodory's Theorem

I am trying to understand the proof of Carathoeodory theorem, I am following the one given by wikipedia. This is what I have understood so far : First we are taking any point then saying it can be ...
0
votes
0answers
17 views

Caratheodory's theorem applied to a disk

Here's the statement that was given in my class. Caratheorody's theorem: Let M $\subset$ $\mathbb R^n$. Then conv$(M)$ is the set of all convex combinations of at most n+1 points from M. Am I ...
18
votes
2answers
311 views

Minimum distance required to travel to “see” all points on a hypercube

You begin on a hypercube of dimension N at the origin i.e. $(0,0,0,0,...,0)$ When at the origin you are able to "see" one and only one step away from you. So from the origin you can see vertices $(1,...
3
votes
0answers
72 views

Is it possible to arrange $p^2$ points on $p^2$ lines so that there are $p$ points on each line?

There are $p^2$ points and $p^2$ lines. Two lines have no more than one intersection point. Is it possible (for any $p$) to arrange the points so that there are $p$ points on each line? For example, ...
0
votes
0answers
49 views

Find largest $a, b \in \mathbb{N}$ so that $a \times b \geq n$

I have the following problem: I have $n$ images that I want to display on-screen. $n$ might be any number from $\mathbb{N}$. If I have one Image, I want this layout (* is an image, _ is empty space): ...
0
votes
2answers
54 views

Example of discrete subspace on a plane which has a closure of continuum? [closed]

I thought that I could take all points with rational coordinates, but this space is not discrete
0
votes
0answers
16 views

Maximum size of an “open convex polygon” made by intersection of lines?

Suppose we have $n$ lines in the plane. What is the maximum size of an "open convex polygon" that we can get from the intersection of lines? For example, in the following picture, we can see an "...
0
votes
1answer
184 views

Tangent lines to polygon on logarithmic time.

I've been reading T.M. Chan algorithm for convex hull of a 2D polygon, here he says that we can find a support line (tangent line) to a polygon given that this polygon is convex and we have its ...
1
vote
2answers
46 views

Changing arrangement of square's vertices with a bijective continuous map in plane.

Is there a continuous bijective map $S:\mathbb{R^2}\to \mathbb{R^2}$ which convert vertices of Square $ABCD$ (respectly arranged points) to vertices of Square $A'C'B'D'$ ? (each points goes to its ...
31
votes
2answers
2k views

How few disks are needed to cover a square efficiently?

A unit square can be covered by a single disk of area $\pi/2$. Let us call the ratio of the square's area to that of the covering disks (i.e. the sum of the areas of the disks) the efficiency of the ...
3
votes
1answer
139 views

Numerical approximation of principal curvature

I have a surface given by z-values on an xy-grid (a 2D-array of values). To calculate surface tension, I need to calculate mean curvature in every point. To calculate mean curvature, I need to ...
0
votes
0answers
19 views

Topological Tverberg Theorem

Topological Tvereberg Theorem says that any continuous function from the $(r-1)(d+1)$-simplex to the $\mathbb{R}^{d}$ identifies $r$ points from $r$ pairwise disjoint faces where $r$ is a prime power. ...
5
votes
1answer
143 views

Two points no matter how you choose from the six points in the unit disk are at distance at most 1?

Six points are to be chosen in a unit disk ($x^2 +y^2 \leq 1$) , such that distance between any two points is greater than 1? I am unable to, I think I want to prove formally that no matter how the ...
2
votes
2answers
193 views

Is circle the only shape which just one of it defined by 3 points in a plain [closed]

I'm curious about shapes which just one of them is determined by a number of points. From an amazing theorem in plain curves geometry we know that vertices of triangles similar to arbitrary triangles $...
8
votes
2answers
78 views

Can all convex $3n$-iamonds be tiled by $3$-iamonds?

Background A polyiamond is a plane figure constructed by joining together equilateral triangles of the same size along their edges. The number of convex polyiamonds is given by A096004. Based on ...
0
votes
2answers
72 views

surface fitting with least square

I want to fit a polynomial surface to some 3d points. First in a loop, matrix R is calculated as follows: ...
3
votes
1answer
220 views

How to discretize a sphere?

I would like to discretize a sphere into icosahedra whose vertices are equidistant, i.e., I want to plot $n$ equidistant points on the surface of a sphere. I am familiar with R, Python, and Matlab. ...
2
votes
0answers
83 views

Is a perfect game of Set always possible?

For anyone not familiar with the game of Set, I'll refer you to the description on this question. My question is this: The game ends when there are no more cards remaining in the deck and there are ...
1
vote
0answers
109 views

Discrete first and second fundamental forms

I want to calculate first and second fundamental coefficients for some points in a point cloud (sampled surface), I used this method (https://arxiv.org/abs/1601.07272) but in this, only three closest ...
0
votes
0answers
35 views

Combinatorial property of cross polytopes [duplicate]

I apologize in advance; I know that this site is for research-level mathematics, not for elementary learning ground. But I tried to understand the following question on my own but it is still ...