Questions tagged [discrete-geometry]

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

Filter by
Sorted by
Tagged with
7
votes
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
2answers
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
0answers
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
3answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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 ...

1
2 3 4 5
25