Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-geometry]

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

21
votes
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
3answers
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
0answers
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
0answers
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
0answers
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
4answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
3answers
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
2answers
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
0answers
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
2answers
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
3answers
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
1answer
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
2answers
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
1answer
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
0answers
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 ...