Questions tagged [discrete-geometry]
Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.
1,996 questions
3 votes
0 answers
87 views
Characterizing polyhedra via "finitely many faces"
I recently tried to see in how far polyhedral geometry can be reduced to the study of convex sets with finitely many faces. In other words, I tried to replace "finitely generated" by "...
- 14.5k
3 votes
0 answers
50 views
Volume of empty lattice simplices and number of integer points in their dilations
Let $S \subset \mathbb{R}^n$ be an $n$-simplex with integer vertices. Suppose that $S$ does not contain any integer point other than its vertices and that $2S$ contains at least one integer point in ...
- 428
1 vote
0 answers
28 views
Prove rigorously a constraint on the efficiency of intermediate segments in a polygonal chain over a regular $k$-grid
Let $k, r \in \mathbb{N}$ with $k \ge 2$ and $r \ge 3$, and let $n_1, n_2, \ldots, n_k \in \mathbb{N}$ satisfy $3 \le n_1 \le n_2 \le \cdots \le n_k$. We define ${G_n}^k := \{0,1,\ldots,n_1-1\} \times ...
- 1,915
5 votes
0 answers
136 views
Do $\binom{n}{2}$ pairs of equi-distances among $n$ points imply a regular $n$-gon?
There are $n$ points on the plane, satisfying that for any two points $A, B$, there is a unique point $C$ lying on the perpendicular bisector of $AB$, i.e. $CA=CB$. Prove or disprove: $n$ is odd, and ...
- 1,073
6 votes
3 answers
281 views
The smallest set of polygonal regions that can all together form 2 different convex polyhedrons
We add a little to On reconstructing convex polyhedrons from disconnected faces that are all mutually non congruent We call a set of polygonal regions that all together form a convex polyhedron a ‘...
- 7,241
3 votes
1 answer
89 views
Properties of a set of infinitely stacked regular tetrahedra
If two regular tetrahedra $S_1$ and $S_2$ in $\mathbb{R}^3$ share a triangular face $f$, we will say that each of them is obtained from the other by stacking over $f$. Now, choose some regular ...
- 31
5 votes
1 answer
172 views
On reconstructing convex polyhedrons from disconnected faces that are all mutually non congruent
Ref: https://arxiv.org/pdf/1307.3472 It is well known that given only a set of convex polygonal regions (call this set of polygons a 'face set') and no further information, one cannot uniquely ...
- 7,241
1 vote
0 answers
111 views
To choose a set of $n$ triangles which together form the largest number of different triangular layouts
Ref: To choose a set of $n$ rectangles which together form largest number of rectangular layouts We present a variant of above question: General Question: given an integer $n$, how do we find $n$ ...
- 7,241
9 votes
1 answer
151 views
Triangulating the cube with small Hamming distance
For a triangulation $T$ of an $n$-dimensional cube, whose vertices are the $2^n$ original vertices, let $d(T)$ be the largest Hamming-distance of two vertices that are in the same simplex. How small ...
- 19.7k
0 votes
0 answers
56 views
To build Heesch-like configurations of 'coronas' around a central triangle with triangles all of same area and perimeter
Ref 1: https://arxiv.org/pdf/1711.04504 Ref 2: On 'Walls' with 'non-tiles' - a variant of the Heesch problem It is known that we cannot tile the plane with triangles that are pairwise ...
- 7,241
2 votes
0 answers
99 views
On 'Walls' with 'non-tiles' - a variant of the Heesch problem
Ref: "Non-tiles and Walls - a variant on the Heesch problem" (https://arxiv.org/pdf/1605.09203) Definitions (adapted from above doc): A non-tile is any polygon that does not tile the ...
- 7,241
3 votes
1 answer
229 views
Tiling the plane with pair-wise non-congruent and mutually similar quadrilaterals
We add a bit to Tiling the plane with pair-wise non-congruent and mutually similar triangles Starting with 2 unit squares and with squares with sides 2,3,5,... (all Fibonacci numbers), one can form an ...
- 7,241
3 votes
0 answers
59 views
Changes to the Delaunay Triangulation after deleting a point inside the convex hull
Consider the Delaunay Triangulation $\mathcal{DT}(P)$ of a finite set $P$ of points in the euclidean plane. let $CH\subset P$ be all points of $P$ that are on $P$'s convex hull, and not just the ...
- 14k
2 votes
0 answers
80 views
Relation of the most distant point-pair to the smallest enclosing circle
I am looking for a counter example to, resp. a proof of the correctness of, the following conjecture: among all pairs points from a finite set in the euclidean plane, that are at maximal distance, ...
- 14k
6 votes
1 answer
290 views
Beardon's version of Poincaré's theorem for fundamental polygons
I am currently trying to understand Beardon's proof for Poincaré's Theorem, which can be found in his book The Geometry of Discrete Groups. The last condition in the theorem is giving me a headache to ...
- 181
3 votes
0 answers
167 views
Are these two definitions of an NTA (nontangentially accessible) domain equivalent? If so, is the constant unchanged?
Jerison and Kenig give the following two conditions (alongside an exterior corkscrew condition, which is not relevant to this discussion) in the definition of an $(M,r_0)$ nontangentially accessible ...
- 221
0 votes
0 answers
105 views
On partitioning convex polygons into kites -2
We add a little to On partitioning convex polygons into kites In his answer to above post, Tom Sirgedas has shown that a convex polygon having two successive angles acute or right is a sufficient ...
- 7,241
0 votes
0 answers
153 views
4-Flower free set family of 3-uniform sets (AKA f(3, 4)) largest construction?
On Polymath, the table shows that the largest known 3-uniform 4-flower free set family has size 38, sourced by this paper. I don't have access to the paper though, and wanted to see the set family ...
- 11
9 votes
0 answers
297 views
Twisted Rupert property
It has recently been proven that the 2017 conjecture that all convex polyhedra $P$ are Rupert is false: "A convex polyhedron without Rupert's property," Jakob Steininger, Sergey Yurkevich. ...
- 153k
3 votes
1 answer
218 views
On partitioning convex polygons into kites
A kite is a quadrilateral with reflection symmetry across a diagonal. A kite with two opposite angles right is a right kite. If a pair of angles in a kite are equal and acute (obtuse), we may say the ...
- 7,241
11 votes
1 answer
661 views
Outside-the-box in 3D: can the $27$ vertices of $\{0,1,2\}^3$ be visited with $13$ line segments connected at their endpoints, without repetition?
This is a variant of the 3D generalization of the well-known Thinking outside the box Nine dots problem I discussed in my previous MO post Optimal covering trails for every $k$-dimensional cubic ...
- 1,915
6 votes
0 answers
111 views
Inequalities Between "m-measure" of Parallelotopes
Let $P \subset \mathbb{R}^n$ be an $n$-dimensional parallelotope generated by $n$ linearly independent vectors $v_1, v_2, \dots, v_n$. For $m \leq n$, I define its $m$-measure $\mu_m(P)$ as the sum of ...
- 61
0 votes
0 answers
78 views
On partitioning convex polygons into mutually congruent spiral polygons
Ref: A claim on partitioning a convex planar region into congruent pieces Definitions: A spiral polygon is a simple polygon with exactly one chain of successive vertices that are all concave. A ...
- 7,241
0 votes
0 answers
136 views
Partitioning planar convex regions into non convex and congruent pieces - 2
We add a little to Partitioning planar convex regions into non-convex and mutually congruent pieces. A rectilinear polygon is a polygon all of whose sides meet at right angles. Thus the interior angle ...
- 7,241
2 votes
0 answers
190 views
Partitioning planar convex regions into non-convex and mutually congruent pieces
For all even $n$, a disc or any rectangle can be (very obviously) cut into $n$ mutually congruent and non convex pieces. Now consider partition into an odd number of pieces instead: Is there any ...
- 7,241
2 votes
1 answer
168 views
Properties of almost additive sets in half-planes inside $\mathbb{R}^2$
A curious combinatorial question appeared whilst thinking about a problem in geometric group theory. Suppose we have an (infinite) set $U \subset \{(x,y) \in \mathbb{R}^2 : y \ge0\} = H \subset \...
- 295
2 votes
0 answers
141 views
Can a laser beam hit all points of $\{0,1,2\}^k \subset \mathbb{R}^k$ using $\frac{3^k-3}{2}$ mirrors only if emitted from outside the open $k$-cube?
Note: I already posted the $3$-dimensional version of this question on Mathematics Stack Exchange, but no answer has been received so far, so I hope that MathOverflow can be a more suitable place in ...
- 1,915
0 votes
0 answers
137 views
Color remapping and solution space intersections in combinatorial Puzzles
Characterizing Solution Space Preservation Under Color Remapping in Combinatorial Puzzles I'm investigating the theoretical properties of color remapping functions on combinatorial puzzles (think ...
2 votes
0 answers
82 views
Is the spectrum of the Hodge-Laplacian unique for a simply connected simplicial complex?
Imagine a 3-dimensional combinatorial simplicial complex, aka "triangulation", which is constructed by simply gluing together "N" tetrahedra via their faces. For simplicity assume ...
- 203
0 votes
1 answer
111 views
To place n points on a planar convex region with average pairwise distance among the points maximized
Given a planar compact convex set $C$ and a number $n$, let us try to put $n$ points in $C$ such that the arithmetic mean of the $n\choose 2$ distances between them is to be maximized. Does this ...
- 7,241
1 vote
2 answers
256 views
Does a convex polyhedron lose vertices when intersected with a translated and scaled copy?
Given a convex polyhedron $P=\{x\in\mathbb{R}^n\mid Hx\leq h\}$, a vector $c\in\mathbb{R}^n$ and a non-negative real number $\alpha\geq0$, is the following statement correct: $$ \#vert(P\cap( c+\alpha ...
- 87
4 votes
2 answers
356 views
On packing vectors in d dimensions
We try to add a bit to Packing obtuse vectors in $\mathbb{R}^d$ given an angle α, in d dimensional Euclidean space, how many vectors can be drawn such that the angle between any pair is at least α? ...
- 7,241
8 votes
2 answers
1k views
Monsky's theorem in 3d
Monsky's theorem, which has a rather fancy proof, states that it is impossible to triangulate a square into an odd number of triangles of the same area. I am interested to find out whether the 3-...
- 12.3k
5 votes
0 answers
238 views
Is there a standardized name for this incidence structure?
Let $m \geq 2$ be a natural number, let $\mathcal{A}$ be any set whose element we call points and let $\mathcal{B} \subseteq \mathcal{P}(A)$ be a set of subsets of $A$ (we call the elements of $\...
- 191
1 vote
1 answer
122 views
On tiling scalene triangles with congruent polygons
For n not a perfect square, are there scalene triangles that can be tiled by n (mutually congruent) polygons? If so, how to characterise them? Which are the values of n such that no triangle (of any ...
- 7,241
0 votes
0 answers
53 views
A question on distribution of affine flats
Let $T_1 = |\{(U_1,U_2) \text{ $|$ } U_1 \text{ and } U_2 \text{ are affine flats of $\mathbb{F}_2^m$ such that } |dim(U_1) - dim(U_2)| \leq 1 \}|$ and T be the total number of affine flats of $\...
- 341
2 votes
1 answer
353 views
Are there triangles that can tile at least one convex n-gon for any value of n?
Ref: https://en.wikipedia.org/wiki/Pinwheel_tiling In a pinwheel tiling of the plane, is it true that for each n>2 there exists some convex n-gon (formed by edges in the layout) that is the union ...
- 7,241
0 votes
0 answers
104 views
Ham-sandwich cut for pseudo configuration of points
I have the following question regarding a generalization of the classical theorem of 'Ham-Sandwich Cut' for pseudo point-configuration. First, a few definitions. A collection of continuous curves in ...
- 1,435
1 vote
0 answers
51 views
Optimal triangulation of points distributed on two parallel lines
Question: what is the fastest algorithm for optimally triangulating a point set $P$ that is given as the union of two sorted sequences $A\cup B\ :=\ ([0,0],[x_{a_1},0],\,\dots,\,[x_{a_m},0],[1,0])\,\...
- 14k
9 votes
2 answers
876 views
On reptiles that are convex and non-parallelogram
A reptile is a shape that can be dissected into smaller copies of the same shape. A reptile is labelled rep-n if the dissection uses n copies. Given any positive n, any parallelogram with sides in ...
- 7,241
2 votes
0 answers
154 views
On ‘special chords’ of convex solids
Ref: On special points within convex solids with all planar sections passing through them having equal area. Definition: Given any convex solid C. For any 2 distinct points on its surface, we have a ...
- 7,241
5 votes
0 answers
142 views
Thrackle for trees
Suppose that we are given in the plane a set of $n$ points, $P$, and $m$ topological trees that pairwise intersect exactly once such that each leaf of each tree is from $P$. Is it true that $m\le n$? ...
- 19.7k
4 votes
0 answers
136 views
Flag spheres, h-polynomials and log-concavity
The following is a major conjecture due to S. Gal Let $\Delta$ be a flag simplicial complex that triangulates a sphere of dimension $d$. Then, the $h$-polynomial, $h_{\Delta}(x) = h_0 + h_1x+\cdots + ...
- 2,289
1 vote
0 answers
159 views
Prove that at least two edges of a polyhedron does not intersect a given plane
The same question was asked on SE https://math.stackexchange.com/questions/5075489/prove-that-at-least-two-edges-of-a-polyhedron-does-not-intersect-a-given-plane Let $P$ be a polyhedron (not ...
- 1,153
0 votes
1 answer
112 views
Convex polyhedra that have a specified set of planar sections
Adding a bit to this question: Regular polygon shadows of convex polyhedra Can one construct a convex polyhedron that has planar sections that are equilateral triangle, square and regular pentagon? ...
- 7,241
1 vote
0 answers
270 views
Combinatorial criteria for when a simplicial complex is a sphere
I am wondering about what is known about the following problem: Let $d\geq 1$ be a fixed integer and let $n\geq d+2$ be an integer. Given a simplicial complex on $n$ vertices, are there known ...
- 63
8 votes
1 answer
257 views
What is geometrically special about an orthogonal lattice (and its $GL(n,{\mathbb Z})$ copies) among all integer lattices?
Let's assume we have a lattice $L \subset {\mathbb R}^n$, given by basis vectors $v^1,v^2,\ldots,v^n$, so $L = \{ \sum_{i=1}^n k_i v^i | k_i \in \mathbb Z \}$. Let's collect all basis vectors into a ...
- 1,426
5 votes
0 answers
109 views
Triangulation with prescribed vertices
It seems that the following statement can be proved using a Voronoi--Delaunay-type argument. Is there a reference? Let $P \subset \mathbb{R}^n$ be a compact subset (it is OK to assume that $P$ is a ...
- 47k
1 vote
0 answers
93 views
Curvature-constrained volume maximization inside regular convex polytopes
Let $P \subset \mathbb{R}^3$ be a convex regular polytope with a finite group of isometries $G \leq \mathrm{Isom}^+(\mathbb{R}^3)$ acting on it. Suppose $P$ admits at least one pair of antipodal ...
- 621
2 votes
1 answer
141 views
Approximate unit distance graphs
Let's suppose we consider a natural relaxation of the definition of a unit-distance graph (UDG): Let $G=(V,E)$ be an $\varepsilon$-approximate UDG in $\mathbb{R}^d$ if there exist points $p_1, p_2, \...
- 645