# Questions tagged [discrete-geometry]

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

1,229
questions

**7**

votes

**2**answers

176 views

### Is a polytope that has in-spheres for faces of all dimensions already regular?

Let $P\subset\Bbb R^d$ be a convex polytope (convex hull of finitely many points).
A $k$-in-sphere of $P$ is a sphere centered at the origin to which each $k$-face of $P$ is tangent. So a 0-in-sphere ...

**9**

votes

**0**answers

101 views

### How much smaller is the Čech complex than the Vietoris-Rips complex?

The Čech complex
is a subcomplex of the
Vietoris-Rips complex.
The V-R complex
includes as a simplex a set of points with pairwise
distances at most $\epsilon$,
whereas the Č complex
includes as a ...

**1**

vote

**1**answer

55 views

### Embedding of spheres which satisfies intersection rules

Let $S = \{S_1, \dots ,S_n\}$ be a finite set of $d$-dimensional spheres with the same radius, and let $E$ be a combination of intersections between them, where an intersection is a rule of the form $...

**1**

vote

**0**answers

67 views

### Lattice points in hypercubes

Let $ (\Lambda_n) $ be a family of lattices, $ \Lambda_n \subset \mathbb{Z}^n $, with $ \det\Lambda_n \sim n $ as $ n \to \infty $ (meaning $ \lim_{n\to\infty} n^{-1} \det\Lambda_n = 1$). I am ...

**3**

votes

**1**answer

39 views

### Tilings of lattice polytopes by transformations of lattice polytopes

A quasi-lattice polytope is a polytope obtained by reflections, translations, and rotations of lattice polytopes. In a tiling of a lattice polytope by quasi-lattice polytopes, are all quasi-lattice ...

**3**

votes

**0**answers

62 views

### Generalized figures of constant width

Is it known which plane figures $Q$ can rotate touching three given circles $A$, $B$, and $C$?
This question was asked by Lazar Lyusternik in 1946, there is only one reference to this paper that ...

**0**

votes

**0**answers

70 views

### On some optimal containers of a set of points on the 2D plane

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find
the smallest semicircular region (semidisk) that contains the points
the smallest ...

**1**

vote

**0**answers

27 views

### Finding a superbase in a lattice of Voronoi first kind

An $n$-dimensional lattice in $\mathbb R^n$ is said to be of Voronoi’s first kind if it there exists $n+1$ vectors $b_1,\cdots b_{n+1}$ (called the superbase) such that
$\{b_1,\ldots,b_n \}$ is a ...

**5**

votes

**1**answer

88 views

### What is known about the duals of cyclic polytopes?

What is known about the duals of cyclic polytopes, in particular, their facets (or equivalently, the vertex-figures of cyclic polytopes)?
In even dimensions, all facets of the dual are ...

**3**

votes

**1**answer

171 views

### Number of points in a lattice and an oblong box

I have a very simple question in geometry of numbers. (It is a slight modification of Counting points on the intersection of a box and a lattice .) There's a bound I can easily prove, and it's good ...

**3**

votes

**1**answer

84 views

### Reference for “every 5-dimensional polytope has a 3-gonal or 4-gonal face”

It seems to be folklore that every 5-dimensional convex polytope has a 3-gonal or 4-gonal face of dimension two. I was not able to track down a source for that claim.
Alternatively, I would be ...

**4**

votes

**1**answer

152 views

### Is there a 4-polytope without 3-gonal and 4-gonal faces, other than the 120-cell?

The question is in the title:
Question: Is there any 4-dimensional polytope without 3-gonal and 4-gonal faces (of dimension two), other than the 120-cell?
I consider only convex polytopes (convex ...

**1**

vote

**0**answers

122 views

### What is the nearest Ford circle for any point in $\mathbb R^2$

I want to draw Ford circles within a "distance Estimated system" (ray marching). Therefore, given a point $(x,y)$ from $\mathbb R^2$, I need the shortest distance to any circle with center $(p/q,1/2q^...

**7**

votes

**0**answers

251 views

### Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?

Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...

**1**

vote

**1**answer

59 views

### What does the extension theorem for tilings state?

I have seen several references to the so-called Extension Theorem in the context of tilings of Euclidean space.
E.g. in "The Local Theorem for Monotypic Tilings" one reads
The Extension Theorem [......

**2**

votes

**1**answer

103 views

### Reference request: placing a set with respect to the integer grid

For $x=(x_1,...,x_n)\in \mathbb{R}^n$, let $Q_x=(x_1,x_1+1)\times ...\times (x_n,x_n+1)$ - the open cube having $x$ in its "bottom left" corner. It seems, I can prove (see a draft here) the following
...

**7**

votes

**0**answers

148 views

### Which convex bodies can be captured in a knot?

Which convex bodies can be captured in a knot?
This question is based on the discussion in "Is it possible to capture a sphere in a knot?".
We assume that the knot is made from unstretchable, ...

**0**

votes

**0**answers

89 views

### How many Shapes are possible to create using Voxels?

Let's suppose I have Big Cube of x cm by y cm by z cm, simmilar to this one:
This big cube is made of tiny little cubes of t cm.
All of this little cubes are transparent, but some of them are red
...

**1**

vote

**0**answers

53 views

### Polytopes with large dihedral angles

The regular $d$-simplex has dihedral angle $\arccos(1/d)<90^\circ$, and the $d$-cube has dihedral angle exactly $90^\circ$.
The maximal dihedral angle of a prism over a $(d-1)$-simplex is also $90^\...

**7**

votes

**2**answers

169 views

### Maximal distance of $2d+1$ points on a sphere

If one arranges $2d$ points on the sphere $\mathbf S^{d-1}\subset\Bbb R^d$ as the vertices of the regular octahedron, then one can achieve a minimal spherical distance of $\pi/2$ between any two ...

**1**

vote

**2**answers

194 views

### A question about dense sets

Suppose that $A$ is a given subset of $I=[0,1],\ $ and
$ \left\{ x_j = \frac{j}{m} \right\}_{j=0}^{m}\ $ is the $m$-partition of $I$, and $\nu(m)$ is the number of
$\ [x_{i-1},x_{i}]\ $ such that $\ [...

**2**

votes

**0**answers

40 views

### Can a polytope with vertex-transitive edge graph or face lattice be made vertex-transitive?

Let $P\subset\Bbb R^d$ be a convex, full-dimensional polytope (convex hull of finitely many points, affine hull is the whole space), $G_P$ its edge graph and $\mathcal F_P$ its face lattice. Any of ...

**2**

votes

**3**answers

216 views

### Number of polytopes formed by connecting points on a hypercube

Fix an integer $d\geq 1$, and let $n\geq 1$. Drawing hyperplanes between all the $d$-sets of lattice points on the boundary of the hypercube $[0,n]^d\subseteq \mathbf{R}^d$ defines a partition of $[0,...

**5**

votes

**1**answer

122 views

### Orientations of triples of points in the plane

Given a finite indexing-set $I$ and a collection $P = \{P_i: \ i \in I\}$ of points in the plane no three of which are collinear, let $I_{(3)}$ denote the set of ordered triples of distinct elements ...

**2**

votes

**1**answer

110 views

### Self-intersecting path of stacked regular tetrahedra

(This question occurred to me after reading
@IanAgol's reminisces
of Conway's spiral tetrahedron billiard path.)
Let $T_i$ be a regular tetrahedron,
and $P$ a collection of regular tetrahedra
glued ...

**1**

vote

**1**answer

85 views

### How to find the optimal lines?

Does anyone know anyway or any algorithm that can exactly and/or
numerically find lines $\left\{ l_{i}\right\} _{i=1}^{n_{k}+2}$ that maximizes $$\min_{1\le i<j\le n_{k}+2}\text{angle}\left(l_{i},...

**1**

vote

**1**answer

120 views

### Another kind of primality related to tessellations by polygons

You can define a number $p$ to be prime by "no tessellation of $p$ identical squares forms a convex figure". This suggests what I'll call a t-prime $p$, defined by "no tessellation of $p$ identical ...

**0**

votes

**1**answer

29 views

### On comparing planar convex regions of equal perimeter and area

Definitions:
The Hausdorff distance between two point sets is the greatest of all the distances from a point in one set to the closest point in the other set.
Given two planar convex regions $C_1$ ...

**0**

votes

**0**answers

21 views

### Optimization problem related to knot placement for parametric interpolation

The problem of knot placement addresses the question of how to choose the parameter intervals $\lbrace[t_i,t_{i+1}]\,|,\, 0=t_0 \leqq t_i\leqq t_{n-1}\leqq t_n=n\rbrace$ in way that renders the ...

**5**

votes

**2**answers

286 views

### On 'fair bisectors' of planar convex regions

Definitions (https://www.ias.ac.in/article/fulltext/pmsc/122/03/0459-0467):
Given a planar convex region $C$ (could be smooth or polygonal), an area bisector of $C$ is any line that partitions $C$ ...

**1**

vote

**0**answers

70 views

### Combinatorial problem in non-collinear chains on tableau $n\times n$

There are $n\times n$ points. How many chains exist in its vertices, in which there is no three collinear points and each point used at most one time.
I have drawn examples below (red is ok but green ...

**1**

vote

**0**answers

153 views

### Let $n \ge 5$. Show that, among the $s_n$ space parts, there are at least $(2n − 3)/4$ tetrahedra (HMO 1973) [closed]

Engel's first problem
Engel's Second problem Proof (problems are from the Hungarian Mathematics Olympiad, 1973).
I'm having problems interpreting the last part of the proof on the second problem. I ...

**2**

votes

**1**answer

96 views

### Densest safe disk packing

Inspired by current regulations regarding the minimal distance to be kept among people to prevent spreading of the COVID-19 virus and the maximal number of people in a group that is not subjected to ...

**2**

votes

**0**answers

55 views

### Uniquely describing a polytopal complex by prescribing the local structure around its vertices

Let $C$ be a $d$-dimensional (abstract) polytopal complex.
Most of what I say below could be asked in this general setting, but for a start, let's further restrict to simple polytopal spheres, that is,...

**1**

vote

**0**answers

56 views

### How large can a planar triangulation be that embeds bi-Lipschitz in a ball of $\mathbb{R^3}$?

Let $G$ be a finite plane graph all bounded faces of which are triangles. For example, $G$ could be
the 1-skeleton of a triangulation of a topological disc. Let $f: V(G) \to \mathbb{R}^3$ be a bi-...

**9**

votes

**1**answer

853 views

### How can we find n points on a plane so that as many pairs of points as possible have the same distance?

There are $n$ points on the plane, and we need to maximize the number of pairs of points which have the same Euclidean distance.

**0**

votes

**1**answer

78 views

### On bounding a certain discrepancy between probability distributions on the symmetric group

Disclaimer. This is a follow up to a question I asked and answered on SE https://math.stackexchange.com/q/3579311/168758. The question was about upper-bounds. Here I'm interested in lower bounds, and ...

**1**

vote

**0**answers

85 views

### Thinnest rigid packings of the plane

A packing of the plane with copies of any shape is called rigid (or "stable") if every unit is fixed by its neighbors, i.e., no unit can be translated without disturbing others in the packing. We are ...

**2**

votes

**1**answer

59 views

### Coordinate-symmetric convex polytopes with equal Erhart (quasi)-polynomials

Recall that given a nondegenerate polytope $P \subset \mathbb{R}^n$ which is the convex set of some vectors with integral coordinates, the Erhart polynomial $p_P(t)$ a polynomial such that $p_P(t)$ ...

**3**

votes

**1**answer

277 views

### Why should it be hard to generalize Dvir's proof of the finite field Kakeya conjecture to the Euclidean case?

Let $q$ be prime and let
$q\delta \sim 1.$ Let $K$ be any set of $Cn\delta$-separated tubes in $B(0,2)$, where $C_n$ is some constant depending on $n$. Let us consider a grid of $q^n$ points scaled ...

**1**

vote

**0**answers

49 views

### Convex Triangulations II

While the original question Convex triangulations was aimed at the existence and calculation of convex triangulations of a given set of $n$ points in the Euclidean plane, I would like to ask the ...

**0**

votes

**0**answers

50 views

### Slices vs harmonic functions — intuition/definitions question

One can identify functions on slices of the boolean hypercube $[n] \choose d$ with harmonic multilinear functions of degree at most $d$.
I don't really understand the intuition behind the harmonic ...

**0**

votes

**1**answer

46 views

### Rule to determine rotationally invariant orders of the points of arbitrary 2d splines

I would like to find a rule to determine the order of the points of arbitrary 2d splines, which should be invariant with respect to rotation (as far as possible).
To illustrate the problem, let us ...

**2**

votes

**0**answers

88 views

### Lipschitz-continuity of convex polytopes under the Hausdorff metric

Recently, I proved the following Lipschitz-continuity like result for convex polytopes:
Let $A\in\mathbb R^{m\times n}$ and $b,b'\in\mathbb R^m$ be given such that $\{x\,|\,Ax\leq 0\}=\{0\}$ (is ...

**1**

vote

**0**answers

63 views

### Regular triangulation of hypercube

I have started studying regular subdivisions of the $n$-cube, and came across the following post: Regularity of Delaunay triangulation of a hypercube.
My question is whether the "standard ...

**3**

votes

**1**answer

52 views

### Uniqueness constraints for Delaunay triangulation

Commonly the assumption that is made on point sets that shall be Delaunay-triangulated is that no three are collinear and no four are cocircular.
Those assumptions are however too restrictive: if ...

**3**

votes

**1**answer

136 views

### Convex triangulations

Given a set of $n$ points in the Euclidean plane of which no three are collinear, does there always exist a convex triangulation and how can one be found algorithmically?
In this context a convex ...

**2**

votes

**0**answers

68 views

### Does there exist a subset $E \in \mathbb{Z}_{p^2}^4$ such that $\Pi(E) \neq \mathbb{Z}_p$?

Denote $\mathbb{Z}_{p^2}$ be the ring residues modulo $p^2,$ i.e
$$ \mathbb{Z}_{p^2} = \left\{ 0,1,2,\dots, p^2-1\right\}.$$
$$\mathbb{Z}_{p^2}^{d} = \underbrace{\mathbb{Z}_{p^2} \times \dots \times ...

**3**

votes

**0**answers

66 views

### Number of orders of distances between points on a line

Points $a_1, a_2, \dots, a_n$ on a line form a set from $n(n-1)/2$ distances between them. Suppose all that distances are different, numerating them from the shortest to the longest one we obtain some ...

**6**

votes

**1**answer

249 views

### A conjecture (or theorem?) on unit vectors in a Euclidean space

I have heard (if I am not mistaken) that there exists the following conjecture (or theorem?).
Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists ...