# 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 - ...

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}...

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 ...

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 $...

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 ...

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 ...

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,\,\...

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 ...

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), ...

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-...

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 $\...

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
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, ...

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 ...

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}...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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$ ...

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 $\...

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 ...

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 $...

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 ...

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$ ...

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 ...

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, ...

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 ...

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 ...

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 ...

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 ...

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}...

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 ...

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 ...

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
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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 \...

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 ...

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 ...