# Questions tagged [discrete-geometry]

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

651 questions
Filter by
Sorted by
Tagged with
18 views

22 views

### Packing & placing rectangles inside a (not-rectilinear) polygon

Intro I have a polygon (not rectilinear) of a fixed size which would act as the container for some number of rectangles. The rectangles are: the same size (height and width) and, they can be rotated ...
1 vote
40 views

### Division of $n$-dimensional simplex [closed]

How many congruent $n$-dimensional simplexes can an $n$-dimensional simplex be divided into? Obviously, a triangle can be divided into $k^2\left(k\in N^*\right)$ congruent triangles (by dividing the ...
1 vote
39 views

### Separation of polyhedra via Farkas' lemma

Let $A\in\mathbb{R}^{m_1\times n}$, $B\in\mathbb{R}^{m_2\times n}$, $a\in\mathbb{R}^{m_1}$, and $b\in\mathbb{R}^{m_2}$. Consider the intersection of an "open" polyhedron and another closed ...
1 vote
33 views

20 views

### Two definitions about reflexive polytopes

I am working through Computing the Continuous Discretely and they give the definition of a reflexive polytope as $$P=\{x \in \mathbb{R}^d : Ax \leq 1\}$$ where all entries from $A$ are integers. It's ...
1 vote
32 views

### Special case of Katchalski's result

Given a family of convex sets in the plane. The intersection of any 4 of them contains a ray (so, we are assuming that the cardinality of the family is at least 4). Prove that the intersection of all ...
28 views

### Maximum diameter $D$ such that all sets of diameter $D$ is covered by unit disc

Given a unit disc what is the maximum diameter $D$ such that all sets of diameter $D$ is covered by the unit disc? I am quite unfamiliar with results from discrete geometry, but I found a result from ...
60 views

• 9,478
1 vote
41 views

### How do points on a grid satisfy the grid equation?

Currently, I'm working on a presentation regarding Penrose tilings. During my research, I've become interested in the Pentagrid method of construction, that was introduced by N.G. de Bruijn in 1981 (...
72 views

### Tucker's lemma, Borsuk-Ulam, triangulating a ball in *truly* antipodally symmetric fashion

I'm attempting to prove Tucker's Lemma from the Borsuk-Ulam theorem by means of the proof sketched as "immediate" on page 36 of Matoušek's Using the Borsuk-Ulam Theorem. In order to do this, ...
36 views

### Maximum number of points with mutually distinct views of a set is $O(n^4)$

I'm looking at the following problem from Jiří Matoušek's Lectures on Discrete Geometry: Let $P = \{p_1, p_2,\dots p_n\}$ be a set of $n$ points in the plane. We say that points $x$, $y$ have the same ...
• 309
1 vote
25 views

### A lower bound for the number of vertices of Voronoi diagram for this set

For a number $n\ge 2$, we define a set of points in $A_{2n}=\{(i,0,0)\in\mathbb{R}^3|1\le i\le n\}\cup\{(0,n,j)\in\mathbb{R}^3|1\le j\le n\}$. What can we say about the number of vertices in the ...
• 309
1 vote
34 views

15 views

### Convex points with diagonals that are parallel to lines formed with convex points and an interior point

We have a set of $2k$ points on a convex hull and connect all of these points to one another with diagonals. Then we add a point $p$ in the interior of the convex hull so that this point is not placed ...
• 243
34 views

### Closest distance between a cube and the slices of a cylinder.

Suppose $B$ is an axis cube aligned in $\mathbb{R}^3$, i.e. the vertices are $0, e_1, e_2, e_3, e_1 + e_2, e_1 + e_3, e_2 + e_3, e_1 + e_2 + e_3$ where $e_1 = (1, 0, 0)$. Suppose $C$ is an infinite ...
• 915
Definition 1: The convex hull of a subset $S$ of $\mathbb{R}^n$ is the smallest convex subset of $\mathbb{R}^n$ that contains $S$. I denote it by the symbol $\mbox{Conv}(S)$. If $S$ is a finite set, i....