# Questions tagged [discrete-geometry]

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

**4**

votes

**0**answers

103 views

### Absolute oscillator in Langton's Ant

We have a simple (or single) block of Langton's Ants colony which includes two ants looking in the same direction. Their positions can be interpreted as knight's walk. The distances between each next ...

**1**

vote

**0**answers

30 views

### Algorithm for Calculating Spheric Convex Hulls of Finite Pointsets

Let the Spheric Convex Hull ($\mathrm{CH}_S$) denote the intersection of all closed spheres that contain a compact $\Sigma\subset\mathbb{R}^n$ and on their boundary at least $n+1$ distinct points of $...

**1**

vote

**2**answers

120 views

### Is a vertex- and edge-transitive polytope already a uniform polytope?

I want to consider (convex) polytopes $P=\mathrm{conv}\{p_1,...,p_n\}\subset\Bbb R^d$ which are both, vertex- and edge-transitive (or maybe stronger: 1-flag-transitive).
Question: Is every such ...

**0**

votes

**0**answers

17 views

### Complexity of Calculating a Generalization of Planar Convex Hulls to Weighted $K_n$

Question:
what is the complexity of finding a unique longest subtour in a $K_n$ with weighted edges,
that is 2-optimal, i.e. its length can't be reduced by exchanging a pair of non-...

**29**

votes

**5**answers

8k views

### Six yolks in a bowl: Why not optimal circle packing? [closed]

Making soufflé tonight, I wondered if the six yolks took on the
optimal circle packing configuration.
They do not. It is only with seven congruent circles that the optimal
packing places one in the ...

**3**

votes

**1**answer

99 views

### Incidences between points and circles in the plane

Suppose we have $n$ points $P$ and $m$ circles $C$ in the plane. Let $I(P,C)=\{(p,c), p \in P, c \in C, p \in c\}.$ Then what do we know about
$\max_{m,n} |I(P,C)|$?
Any references?

**3**

votes

**0**answers

121 views

### Can bellows make loops?

Can flexible polyhedron (hyperbolic or euclidean) have non-simply connected configuration space not containing singular polyhedra?

**1**

vote

**0**answers

67 views

### Are there half-transitive convex polytopes?

I only consider convex polytopes, i.e. convex hulls of finitely many points. The (edge-)graph of a polytope $P\subseteq\Bbb R^d$ is the graph consisting of the polytope's vertices, two are adjacent if ...

**3**

votes

**1**answer

71 views

### Generalized digraph homomorphisms and graph cores

Given any digraphs $G$ and $H$ we say a surjection $f:V(G)\to V(H)$ reduces $G$ to $H$ if and only if it satisfies $(u,v)\in E(G)\iff (f(u),f(v))\in E(H)$. Where if there exists at least one ...

**1**

vote

**0**answers

45 views

### Barycentric weighting of a point in a mesh

I know there is a way to get a barycentric weighting of a point $p$ inside a convex polygon; for weighting $\omega_n$ of component $q_n$ with adjacent angles $\gamma_n$ and $\delta_n$:
$$\omega_n = \...

**8**

votes

**1**answer

255 views

### Integer points avoiding three on a line, four on a circle

A century ago, Dudeney asked to place $16$ pawns on a chessboard with no three
on a line:
As described by David Eppstein,1 the maximum number $g_3(n)$ points that
...

**22**

votes

**1**answer

413 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

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

**14**

votes

**1**answer

585 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

73 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

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

**10**

votes

**0**answers

176 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

37 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

160 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

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

**8**

votes

**2**answers

359 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

202 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

60 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

103 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

266 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

215 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

23 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

79 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

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

**14**

votes

**1**answer

279 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

979 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

214 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

81 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

57 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

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

**4**

votes

**0**answers

101 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

215 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

57 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

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

**13**

votes

**0**answers

254 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

65 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

270 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

33 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

117 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

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