Questions tagged [discrete-geometry]
Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.
1,482
questions
0
votes
0
answers
40
views
The closest ellipse and circle to a given triangle - 2
We add a little more to The closest ellipse to a given triangle.
The above linked discussion used the Hausdorff distance to quantify how close two planar convex regions are.
In an earlier post - ...
- 4,319
0
votes
0
answers
23
views
Product between graphs preserving the product shortest path metric
Let $\{G_i:=(E_i,V_i,W_i)\}_{i=1}^N$ be a weighted graphs and $N\ge 2$ be an integer. Is there a notion of "graph product" $G$ of $\{G_i\}_{i=1}^N$ for which
$$
d_G((u_i)_{i=1}^N,(v_i)_{i=1}...
- 4,831
3
votes
0
answers
100
views
Can a polytopal graph be "centrally symmetric" in more than one way?
Let $P,Q$ be two centrally symmetric convex polytopes, potentially of different dimensions and combinatorial type, but with the same edge-graph $G$.
The central symmetry of $P$ induces an involutory ...
- 11.2k
1
vote
1
answer
130
views
Bound for a sequence of vertices in a graph
I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $...
- 135
1
vote
0
answers
35
views
Tiling the hyperbolic plane with mutually-non congruent equal area triangles
This post continues On tiling the plane with non-congruent, equal area triangles with each edge having a unique length
Can the hyperbolic plane be tiled by pair-wise non-congruent equal area ...
- 4,319
0
votes
0
answers
40
views
On tiling the plane with non-congruent, equal area triangles with each edge having a unique length
Ref: Tiling with incommensurate triangles shows an approach for tiling with incommensurate triangles - all sides and all angles unique and also with different areas - with the perimeters of the tiles ...
- 4,319
0
votes
1
answer
35
views
Constructing a polygon from another with collinearity constraints
Let $P$ be a closed polygon defined by the sequence
$p_0,\,\dots,\,p_{n-1},p_0$ of points.
Question:
how can one construct, with straightedge and compass alone, another sequence of points $q_0,\,\...
- 11.7k
1
vote
0
answers
42
views
Chromatic number of 2-graph vs hypergraph of point-line incidences
Define the chromatic number $\chi(H)$ of a (hyper)graph $H$ as the smallest $k$ such that its vertices can be $k$-colored such that no (hyper)edge is monochromatic.
Given a finite set of points $P$ in ...
- 17.7k
1
vote
0
answers
41
views
Kissing behavior of planar regions
This post reworks a question that was stated in a slightly different form at Convex region $C$ with least kissing number of copies of $C$.
Background: Given a 2D region $C$ (not necessarily convex), ...
- 4,319
3
votes
0
answers
64
views
Is the face poset of a compact intersection of cylinders and half-spaces shellable?
Let the $n$-disk $D^n$ be stratified hemispherically (so there are two 0-dimensional strata at the poles, two 1-dimensional strata for the prime meridian and the international date line, two 2-...
- 53.7k
0
votes
0
answers
21
views
What is the most dense sample for which the Crust algorithm returns an incorrect polygonal reconstruction?
The Crust algorithm by Amenta, Bern, and Eppstein computes a polygonal reconstruction of a smooth curve $C$ without boundary from a discrete set of sample points $S$. It is known that if $S$ is an a $\...
- 383
2
votes
1
answer
71
views
On equipartitions of surfaces of 3D convex regions
Let S be the surface of a 3D convex region (a 'convex surface'). Let S' be a subset of S. We shall refer to S' as geodetically convex in S if the following condition holds: If A and B are two points ...
- 4,319
4
votes
0
answers
119
views
Can a convex frame hold all circles of radius $1/n$ immobile?
Here is a frame that holds circles of radius $1, \frac{1}{2}, \frac13, ..., \frac17$ immobile.
By "immobile", I mean no circle can move without overlapping other circles or the frame, ...
- 1,143
8
votes
1
answer
206
views
For which $n$ does a y-formed $n$-polyomino tile a $n \times n \times n$-cube?
I got from my children as a gift a puzzle consisting of 25 y-shaped 5-polyominoes that form a $5 \times 5 \times 5$-cube (see picture).
I'm wondering for which $n$ does a y-formed $n$-polyomino tile a ...
- 3,916
2
votes
1
answer
119
views
How many ways are there to pick $n$ points on the finite affine plane $(\Bbb F_q)^2$ such that no three are collinear?
How many ways are there to pick $n$ points on the finite affine plane $(\Bbb F_q)^2$ such that no three are collinear?
For example, how many ways can we pick $5$ points on $\Bbb F_{32}\times\Bbb F_{32}...
- 798
0
votes
1
answer
43
views
On 'axiality' of planar convex regions
Axiality has been studied under a definition given here: https://en.wikipedia.org/wiki/Axiality_(geometry)
Consider an alternative definition of axiality as follows: For a convex region C, consider a ...
- 4,319
1
vote
0
answers
13
views
Regular covering of planar pointsets with convex polygons
Question:
What is known about the problem of covering a finite set of $\mathbb{P}$ of points in the plane with convex polygons
that have the same number $m$ of points from $\mathbb{P}$ as corners
and ...
- 11.7k
14
votes
1
answer
667
views
Are there general principles that allow us to easily determine whether coins in simple arrangements in a frame can move?
Circular coins in a frame may all be stuck in their positions; for example:
Another possibility is that they can all move simultaneously; I claim the following examples:
It is not always obvious ...
- 1,143
0
votes
0
answers
165
views
Covering discrete triangle with generalized knight jumps
Consider for $n\in\mathbb{N}, n\geq 6$ the discrete triangle $\nabla=\{(i,j)\in \{1,\ldots,n-1\}^2 \mid j\leq n-i\}$. This is basically the lower "half" of a chess board if you cut it along ...
- 63
15
votes
1
answer
952
views
Conjecture: If equal size circular coins are in a convex polygonal frame, with each coin touching exactly one edge, then all the coins can move
Earlier I conjectured that if circular coins of any sizes are in a convex polygonal frame, with each coin touching exactly one edge, then all the coins can move. A counter-example using coins of ...
- 1,143
38
votes
2
answers
3k
views
Conjecture: If circular coins of any sizes are in a convex polygonal frame, with each coin touching exactly one edge, then all the coins can move
Suppose some circular coins (not necessarily the same size) are in a frame. The coins may be immobile, as in this example:
On the other hand, they may be free to move, as in these examples (in which ...
- 1,143
0
votes
0
answers
28
views
Smallest centrally symmetric containers of planar regions - 2
This post adds a bit to Finding the smallest centrally symmetric region that contains a convex planar region . In his answer there, Jukka Kohonen observed: Given a planar convex region $C$, the ...
- 4,319
1
vote
0
answers
101
views
Which vector configurations generate as zonotope the regular $2n$-gon?
For $X=(x_1,\dots,x_n) \in (\mathbb{R}^2)^n$, the generated zonotope (zonogon in 2D) is defined by
$ Z(X) := \{\sum_{k=1}^n \sigma_k x_k
: \sigma_1,\dots,\sigma_n \in [0,1] \}. $
Which $X$ ...
- 91
5
votes
1
answer
225
views
Counting points above lines
Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\...
- 18.1k
3
votes
1
answer
93
views
Constrained morphing of polygons
This post continues 'Constrained morphing' of planar convex regions
If an $m$-gon $P_m$ is to be morphed (altered continuously) into an $n$-gon $P_n$ with same area and perimeter, can one ...
- 4,319
2
votes
1
answer
74
views
'Constrained morphing' of planar convex regions
Morphing may be defined as a continuous transition of one shape to another. This post is about modifying planar regions continuously from one form to another under some constraints.
Qn: If $C_1$ and $...
- 4,319
1
vote
0
answers
31
views
Possible extensions of the perpendicular axes theorem for moment of inertia
This post continues on Moment of inertia from Bisectors and partitioning lines for convex regions defined with respect to the moment of inertia.
The perpendicular axis theorem states that the moment ...
- 4,319
1
vote
0
answers
29
views
Computational hardness of a discrete generalized rectangle packing problem
I have a decision problem that is clearly in NP, but I cannot seem to prove that it is in P, nor can I prove its NP-hardness. I attribute this more to my inexperience than to the problem's difficulty (...
2
votes
1
answer
48
views
Counting the number of pair of d-uplets with upper bounded distance
Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...
- 55
1
vote
0
answers
34
views
Bisectors and partitioning lines for convex regions defined with respect to the moment of inertia
Ref: Mathematical Omnibus by Fuchs and Tabachnikov, Lecture 11.
Consider any planar convex region C. A line l may be called an inertia bisector of C if it divides C into 2 pieces each of which has ...
- 4,319
13
votes
0
answers
210
views
Regular $n$-gon with diagonals: bounds on area of largest cell?
Consider a regular $n$-gon of side length $1$ with diagonals. Here is an example with $n=11$ (from geogebra applet).
I've been trying to find, in terms of $n$, bounds on the area of the largest cell, ...
- 1,143
3
votes
1
answer
184
views
How much of an aperiodic tiling is needed to force aperiodicity?
Consider an aperiodic tiling. By definition, there is a $C$ such that, for any box of side $C$, the part of the tiling contained in the box can be continued to the whole plane only in a non-periodic ...
- 18.1k
14
votes
1
answer
215
views
How many distances are required to calculate all distances among $n$ points in the Euclidean plane?
I want to know all the pairwise distances between points $P_1,P_2,\ldots,P_n$ in the Euclidean plane (or equivalently, I want to reconstruct the set of points up to congruence). Let's say I have an ...
- 513
13
votes
2
answers
523
views
How to characterize the regularity of a polygon?
In my research, I've recently started to play with Voronoi tessellations. I currently have a Python code that creates the tessellation and I am trying to color the polygonal regions according to their ...
- 141
0
votes
0
answers
56
views
Number of tiles inside a region of a hyperbolic tiling
Let $\mathbb{D}$ be the Poincare disc model of hyperbolic geometry with $\{p,q\}$ tiling on it.
In this, paper authors calculated the number of tiles on any circular region centered at a vertex or ...
- 169
2
votes
0
answers
68
views
Is parquetability decidable?
Let $T\neq \emptyset$ be a finite subset of $\mathbb{Z}\times\mathbb{Z}$. We say that $\mathbb{Z}^2 = \mathbb{Z}\times\mathbb{Z}$ is parquettable by $T$ if there is a partition $\frak P$ of $\mathbb{Z}...
- 41.4k
1
vote
1
answer
118
views
What properties are preserved by quasi-isometries
Recently, I came across the notion of quasi-isometries, while thinking of "discrete spaces which are surrogates for approximate continuous ones".
What (metric)/geometric properties are ...
- 4,831
2
votes
0
answers
106
views
Can a laser hit all the mirrors out of order?
For this question, a "cycle" is a sequence of distinct points
$X = (x_1,x_2,\cdots,x_k)\in\mathbb{R}^3$ which defines a piecewise linear path starting at $x_1$ and visiting the points in ...
- 317
4
votes
0
answers
134
views
On moments of inertia of planar and 3D convex bodies
The following observation can be readily proved using the perpendicular axes theorem and intermediate value theorem: "Given any planar figure C, through any point on it, there is at least one ...
- 4,319
4
votes
2
answers
224
views
Discrete isoperimetric problems
It is well-known that among all planar curves, the circle — invariant under $O(2)$ — has the best isoperimetric ratio. Similarly, among all $n$-gons, the regular $n$-gon — invariant under the dihedral ...
- 479
1
vote
1
answer
48
views
Relation of MSTs in the Euclidean plane to Delaunay triangulations
It is known that the Minimum Spanning Tree (MST) of a finite set of points in the Euclidean plane is contained in the point set's Delaunay triangulation, but is that all that can be said about their ...
- 11.7k
5
votes
1
answer
172
views
Which pyramids fill space?
Let us define a pyramid as a convex polyhedron with one quadrilateral face and four triangular faces.
Question: How many pyramids (or families of pyramids) are known that can fill 3D space without ...
- 4,319
15
votes
0
answers
208
views
Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?
Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation
it stays a convex polytope,
it stays a combinatorial dodecahedron (i.e. its ...
- 11.2k
6
votes
0
answers
73
views
Tiling the plane with mutually non-congruent equal area rectangles
Question: Is it possible to tile the plane with mutually non-congruent rectangles all of equal area?
Note 1: If the answer is "yes" then, there could be constrained versions of the question ...
- 4,319
1
vote
0
answers
74
views
Lattice packing
Let $\Lambda$ be a lattice in $R^n$ and $R>0$ a real number.
Consider the number $N$ of points in $\Lambda$ of norm less than $R$. Let $R$ goes to infinity. What can be said about the asymptotic ...
- 229
3
votes
0
answers
181
views
Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets
Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
- 1,539
3
votes
1
answer
98
views
Distance of average of points to center of minimum enclosing ball
Let $v_1, ..., v_n$ be distinct points in $\{0,1\}^d$ with the same norm $\|v_i\|_2=k$ (i.e each $v_i$ has $k$ ones). Let $A=\frac{1}{n}\sum_{i=1}^n v_i$ be their average, and let $C$ be the center of ...
- 432
7
votes
0
answers
141
views
Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets
We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
- 1,539
0
votes
0
answers
43
views
Tiling with non-congruent triangles all of which have an equal angle and equal area
Reference 1: an earlier question on tiling with pair-wise non-congruent tiles: Tiling with triangles of same circumradius and inradius
Reference 2: Triangulation of polygons with all triangles having ...
- 4,319
0
votes
0
answers
77
views
Upper bound on the diameter of a convex lattice n-gon with a given area
Given the area $A$ of a strictly convex polygon with $n$ vertices with integer Cartesian coordinates, there are usually several non-equivalent polygons. The relationship between the area, the number ...
- 176