# Questions tagged [discrete-geometry]

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

**21**

votes

**1**answer

295 views

### Is there a short proof of the decidability of Kepler's Conjecture?

I've believed that the answer is "yes" for years, as suggested in various sources with reference to Tóth's work. For example, the Wikipedia article for Kepler Conjecture says:
The next step toward ...

**2**

votes

**0**answers

69 views

### Existence of a “generic enough” lattice point interior to a lattice triangle

Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a ...

**13**

votes

**1**answer

477 views

### Holes in double-tileable polynominoes

This question was communicated to me by Evgeniy Romanov.
Consider a connected polyomino $P$ that can be completely tiled in two different ways: with disjoint $2 \times 2$ square tetraminoes, and with ...

**1**

vote

**1**answer

48 views

### How do I find the correct distance spacing for distributing equidistant points on a sphere of a given diameter?

How do I find the correct distance spacing for distributing equidistant points on a sphere of a given diameter?
I don't need to fill the sphere with equidistant points. I just need less than a ...

**1**

vote

**0**answers

32 views

### Shortest Lattice Vector with restricted $x$

Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.
My questions ...

**9**

votes

**0**answers

164 views

### Fundamental circuit characterization of matroid independence complexes

I have the following characterization of independence complexes of matroids, which I think is standard but I can't find a reference. Here it goes:
A pure simplicial complex $\Delta$ is the ...

**1**

vote

**0**answers

28 views

### Compute the edge-skeleton of a polytope given by its vertices

Let $P$ be a polytope given by a vertex description, i.e., $P=conv(\{x_1,\ldots,x_m\})\subset\mathbb{R}^n$.
Is there an efficient (i.e., not relying on Linear Programming) algorithm to compute the ...

**1**

vote

**0**answers

153 views

### Acute triangles from 100 points

Given $n$ points in general position in the plane, let $P_n$ be the maximum proportion of the $\binom{n}{3}$ triangles with three acute angles. What is the limit $\lim\limits_{n \rightarrow \infty} ...

**5**

votes

**0**answers

40 views

### Universal point sets for 1-plane graphs

It is a notorious open problem to find a smallest set of $N$ points that
permit any $n$-vertex planar graph to be drawn in the plane without
crossings, using only those $N$ points as vertices, and ...

**7**

votes

**1**answer

278 views

### Simplicial set are to cubical sets what simplicial complexes are to …?

Simplicial sets and cubical sets (with or without connections) are defined as presheaves over some indexing categories. There is a full subcategory of simplicial sets that we can identify with the ...

**1**

vote

**0**answers

30 views

### Defining a notion of “volume of its lattice” for non-rational subspaces

Let $V\subseteq \Bbb R^n$ be a vector subspace. If $V$ is rational, i.e. has a basis consisting of elements in $\Bbb Z^n$, then there’s a well-defined notion of the “volume of the lattice of V”:
$$\...

**8**

votes

**3**answers

198 views

### Random reflections unexpectedly produce banded distributions

Start with $p_1$ a random point on the origin-centered unit circle $C$.
At step $i$, select a random point $q_i$ on $C$, and a random mirror line
$M_i$ through $q_i$, and reflect $p_i$ in $M_i$ to ...

**1**

vote

**0**answers

56 views

### On Topological Tverberg Theorem

Let $r$ be a prime power. The Topological Tverberg Theorem says that any continuous map from a $(r-1)(d+1)$-simplex to $\mathbb{R}^d$ identifies points from $r$ disjoint faces. It is not hard to see ...

**6**

votes

**0**answers

102 views

### Does the problem of recognizing 3DORG-graphs have polynomial complexity?

A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...

**9**

votes

**0**answers

261 views

### Why does Loday call the permutohedra “zylchgons”?

Today I was reading Jean-Louis Loday's classic paper, "Realization of the Stasheff polytope", in which he produces a simple and very pretty realization of the associahedra as convex polytopes. He ...

**5**

votes

**4**answers

210 views

### Lattice points in a square pairwise-separated by integer distances

Let $S_n$ be an $n \times n$ square of lattice points in $\mathbb{Z}^2$.
Q1. What is the largest subset $A(n)$ of lattice points in $S_n$ that have the
property that every pair of points in $A(n)$...

**7**

votes

**0**answers

28 views

### Inefficient covering by translates

While trying to answer this question, I arrived at another question:
How many translates of $\{0,1\}^n$ does it take to cover $\mathbb F_3^n$?
The broader context is: consider a set $S$ and a ...

**2**

votes

**0**answers

22 views

### condition on rational polyhedral cone to guarantee dual cone is homogeneous

Let $\sigma\subseteq \Bbb R^d$ be a full-dimensional rational polyhedral cone which is strongly convex (i.e. $\sigma\cap-\sigma=0$).
Definition. The cone $\sigma$ is homogeneous if there are ...

**5**

votes

**0**answers

74 views

### Random walks in arrangements of lines in the plane

Let $\cal{A}_n$ be a simple arrangement of $n$ lines in $\mathbb{R}^2$.
(Simple: each pair of lines meet in a distinct point, i.e.,
no three lines pass through the same point.)
Start a random walk at ...

**5**

votes

**0**answers

143 views

### Can we represent partitions by mutually parallel lines in the plane?

Lately I have become interested in the following idea: Suppose $n$ is a positive integer and $[n]=\{1,2,3,...,n\}$. Suppose we have 3 distinct partitions $b$, $g$, and $r$ of $[n]$. Assume that the ...

**13**

votes

**1**answer

274 views

### Can the graph of a symmetric polytope have more symmetries than the polytope itself?

I consider convex polytopes $P\subseteq\Bbb R^d$ (convex hull of finitely many points) which are arc-transitive, i.e. where the automorphism group acts transitively on the 1-flags (incident vertex-...

**19**

votes

**2**answers

967 views

### Is it possible that both a graph and its complement have small connectivity?

Let $G=(V,E)$ be a simple graph with $n$ vertices. The isoperimetric constant of $G$ is defined as
$$
i(G) := \min_{A \subset V,|A| \leq \frac n2} \frac{|\partial A|}{|A|}
$$
where $\partial A$ is ...

**1**

vote

**0**answers

43 views

### Upper bounds on $\epsilon$-covers of arbitrary compact manifolds

Let $M \subset \mathbb{R}^d$ be a compact $k$-dimensional manifold embedded in $\mathbb{R}^d$. Let $\mathcal{N}(\epsilon)$ denote the size of the minimum $\epsilon$-cover $P$ of $M$, that is for every ...

**8**

votes

**3**answers

212 views

### monochromatic subset

Suppose we have $n^2$ red points and $n(n-1)$ blue points in the plane in general position. Is it possible to find a subset $S$ of red points such that the convex hull of $S$ does not contain any blue ...

**2**

votes

**1**answer

76 views

### Combinatorial problem about binary arrays with certain mutual distinctions

If there are m binary arrays (with 0 and 1) of length n, and between any two of these m arrays, there are k and only k same numbers (with the same site index in two different arrays). For example, if ...

**2**

votes

**0**answers

56 views

### 8-partition of a planar convex body by 4 concurrent lines

It is known1 that any convex body $K$ in the plane can be
partitioned into $6$ equal-area pieces by $3$ concurrent lines
which meet at a point in $K$.
Call this a $6$-partition.
This result cannot be ...

**1**

vote

**1**answer

160 views

### A possible characterization of the cube?

Let $P$ be the $1$-skeleton of a convex polyhedron fixed in $\mathbb{R}^3$,
and $|P|$ the sum of the Euclidean lengths of the edges of $P$.
Let $P_1, P_2, P_3$ be the perpendicular projections of $P$
...

**3**

votes

**0**answers

93 views

### Generating a Penrose tessellation around a given tile

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it.
The following picture illustrates the request:
In this example, the starting tile is a "thin rhombus" (the pink ...

**3**

votes

**2**answers

214 views

### Minimum weight triangulation of lattice points in a circle

Let $r$ be a natural number, and consider the $\mathbb{Z}^2$ lattice points
$S$ inside or on the circle $C$ of radius $r$ centered on the origin.
Let $P$ be the convex hull of $S$; so $P$ is inscribed ...

**0**

votes

**0**answers

24 views

### Integer Distances in Pointsets Generated from Simplices with Integer Sidelengths

Let $\mathbb{S}_\mathbb{N}^n$ denote the set of all $n$-simplices in $n$-dimensional euclidean space $E^n$.
Call an $n$-simplex aligned, if the set $C$ of its corners satisfies
$\exists c_k=\left(x^...

**2**

votes

**0**answers

50 views

### Can projecting a simplex onto orthogonal subspaces exposes the same vertices and edges?

Given the regular $n$-dimensional simplex $S\subset\Bbb R^n$ with $n\ge 4$, as well as two orthogonal subspaces $V,W\subset\Bbb R^n$ of dimension $\ge2$ (not necessarily of same dimension, not ...

**5**

votes

**1**answer

192 views

### Can two non-equivalent polytopes of same dimension have the same graph?

By a polytope I mean the convex hull of finitely many points. The graph of a polytope is the graph isomorphic to its 1-skeleton. By equivalence of polytopes I mean combinatorial equivalence, i.e. ...

**12**

votes

**0**answers

249 views

### Simple disproof of Danzer — Grünbaum conjecture

I asked this question on the MSE, but I did not get an answer. I hope that one of the experienced participants will check the correctness of the proof or the truth of the statement (and, perhaps, will ...

**3**

votes

**0**answers

61 views

### Reconstructing plane graphs from degree- and face-sequences

Let $G$ be a plane $3$-connected graph; so it partitions the plane
into regions bounded by faces.
Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$,
and $\mathrm{deg}_f$ be the sequence of ...

**5**

votes

**2**answers

238 views

### Is every polytope combinatorially equivalent to the intersection of a simplex and a linear subspace?

I wonder whether such a result is known, and if so, whether the proof is trivial.
By polytope I mean the convex hull of finitely many points in $\Bbb R^n$. Assume the simplex to be symmetric and ...

**1**

vote

**0**answers

55 views

### Can sufficiently symmetric polytopes be uniquely reconstructed from their 1-skeleton?

General convex polytopes can not be uniquely reconstructed from their 1-skeleton1, as explained here. Not even the dimension is known from the skeleton, as e.g. the complete graph $K_n,n\ge 5$ is the ...

**0**

votes

**0**answers

29 views

### How many points are still contained in a common (hyper-)ellipsoid?

It is known that
$${d+2\choose 2}-1$$
points uniquely determine a quadric in $\Bbb R^d$. However, I want my points not on an arbitrary quadric, but on a centered hyperellipsoid in $\Bbb R^d$, or ...

**5**

votes

**0**answers

115 views

### Polychromatic number of plane

Let $\chi$ be the least size of a partition of plane into pieces each of which omits unit distance. Let $\chi_p$ be the least size of a partition of plane into pieces each of which omits some distance....

**2**

votes

**1**answer

184 views

### Name and Algorithms for a Sparsest Circle Packing

The ordinary circle packing problem in the variant with equal radii asks for the largest radius $r_{max}$ that allows placing $n$ non-overlapping circles with radius $r_{max}$ e.g. in the unit square, ...

**5**

votes

**0**answers

164 views

### How to pack 27 $a\times b\times c$ blocks into a cube of side $a+b+c$ with some kind of symmetry?

Recently I stumbled on the problem quoted here about a geometric proof of the AM-GM inequality $$(a_1+\cdots+a_n)^n\ge n^n a_1\cdots a_n$$ by packing $n^n$ rectangular $ n$-dimensional boxes of sides $...

**7**

votes

**2**answers

241 views

### Visual proof of convergence for Steiner's symmetrization

I want to find a visual proof of the following fact:
For any convex figure in the plane there is a sequence of Steiner's symmetrizations that makes it arbitrary close to a circular disc.
All ...

**6**

votes

**1**answer

136 views

### Tiling with incommensurate triangles

Say that two triangles are incommensurate if they do not
share an edge length or a vertex angle, and their areas differ.
Suppose you'd like to tile the plane with pairwise incommensurate triangles.
I ...

**9**

votes

**2**answers

244 views

### Counting Hamiltonian cycles in $n \times n$ square grid

I wonder if anyone has counted these curves, either exactly or asymptotically?
Let $S_n$ be an $n \times n$ subset of $\mathbb{Z}^2$ consisting of $n^2$
lattice points: a lattice square.
Define a ...

**3**

votes

**0**answers

186 views

### Shapes defined by points

Can shapes determined by number of points?
From an amazing theorem in plane curves geometry we know that vertices of triangles similar to arbitrary triangle $T$ is dense on every closed jordan curve ...

**4**

votes

**2**answers

129 views

### Counting points and lines in a plane

Let $P_1$ be a set of 4 points in the Euclidean plane. Formally, $P_1$ determines a set $L_1$ of 6 lines, which then determine only 3 points not already in $P_1.$ Let $P_2$ be the set of 7 points ...

**1**

vote

**3**answers

208 views

### Repeatedly halve and twist a planar shape: Limiting shape?

Consider the following iterative process.
Start with a planar region $R=R_0$ of $\mathbb{R}^2$.
I am thinking of $R$ as connected,
but it may become disconnected.
In the example below, $R$ starts as ...

**15**

votes

**1**answer

253 views

### Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...

**5**

votes

**2**answers

173 views

### The number of co-circular four tuples

Let $A,B ⊂ \mathbb{R}$ such that $|A| = |B| = n$. What is the best-known upper bound on the number of four-tuples in $A \times B$ where the four points are co-circular, they lie on the same circle?

**1**

vote

**1**answer

78 views

### Coloring lines in plane

We assume that all the lines in the plane are each colored with one of two colors: red or blue. Given angle $\alpha.$
My question 1. Is there possible to get two lines with the same color and angle ...

**8**

votes

**0**answers

86 views

### Counting symmetric convex bodies with no nonzero lattice point in the interior

In order to estimate the size of the torsion in the algebraic $K$-groups of $\mathbb Q$ one needs to understand the homology of $\mathrm{GL}_n(\mathbb Z)$, or alternatively, the homology of the space ...