Questions tagged [discrete-geometry]

Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.

Filter by
Sorted by
Tagged with
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 ...
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 ...
  • 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 ...
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 ...
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}...
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 ...
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 ...
  • 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 ...

1
2 3 4 5
30