Questions tagged [discrete-geometry]

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

264 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
39
votes
0answers
646 views

Extending a line-arrangement so that the bounded components of its complement are triangles

Given a finite collection of lines $L_1,\dots,L_m$ in ${\bf{R}}^2$, let $R_1,\dots,R_n$ be the connected components of ${\bf{R}}^2 \setminus (L_1 \cup \dots \cup L_m)$, and say that {$L_1,\dots,L_m$} ...
32
votes
0answers
1k views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\...
24
votes
0answers
639 views

Minimal number of intersections in a convex $n$-gon?

For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...
22
votes
0answers
577 views

How much of the plane is 4-colorable?

In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
21
votes
0answers
518 views

A combinatorial approximation functor sSet->qCat

Let $sSet_J$ denote the category of simplicial sets equipped with the Joyal model structure. Simply by the fact that $sSet_J$ is locally presentable and its class of anodynes ($\neq \mathbf{Cof} \cap ...
20
votes
0answers
227 views

Can 4-space be partitioned into Klein bottles?

It is known that $\mathbb{R}^3$ can be partitioned into disjoint circles, or into disjoint unit circles, or into congruent copies of a real-analytic curve (Is it possible to partition $\mathbb R^3$ ...
18
votes
0answers
969 views

Hrushovski's Construction

Zilber expressed a conjecture for $\aleph_{1}$- categorical theories (In the 80s). Zilber's Conjecture: The geometry of any $\aleph_{1}$- categorical structure is one of the following: (a) Trivial (...
17
votes
0answers
408 views

Large almost equilateral sets in finite-dimensional Banach spaces

Question: Does there exist a function $C:~(0,1)\to (0,\infty)$ such that for each $\varepsilon\in(0,1)$ every Banach space $X$ of dimension $\ge C(\varepsilon)\log n$ contains an $n$-point set $\{x_i\...
16
votes
0answers
222 views

Precise estimate for probability an $n$-point set has diameter smaller than $1$

This question was inspired by an earlier question that I answered but would like a more precise bound for. Consider random points $x_1, \dots, x_n$ in the unit ball in $\mathbb R^d$, uniformly and ...
15
votes
0answers
554 views

Knight's tours in higher dimensions

I wonder if Knight's Tours have been explored in higher dimensions, using the following definition of a knight move. In dimension $d=2$, the knight moves left/right and forward/back one step and two ...
15
votes
0answers
445 views

Expanding disks lead to what packing of the plane?

Suppose one sprinkles points uniformly at random on the infinite Euclidean plane, with some density $\rho$ per unit area. View the points as disks of radius zero. Now the radii $r$ of all disks grows ...
15
votes
0answers
557 views

Does every connected set that is not a line segment cross some dyadic square?

A dyadic square is a subset of $R^2$ of the form $x + 2^{-n} [0,1]^2$ with $x \in 2^{-m} Z^2$, for integers $m,n \geq 0$. We say that a set $A$ crosses a square $S$ if there exists a connected subset ...
15
votes
0answers
2k views

Covers of $Z^k$

This is a question related to covers of $Z^\infty$. Is it possible to cover $Z^k$, $k>1$, with the $l_1$-metric by a constant (not depending on $k$) number of collections of subsets $U^0,...,U^c$ ...
14
votes
0answers
453 views

Grothendieck on polyhedra over finite fields

In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most singular ...
13
votes
0answers
279 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 ...
13
votes
0answers
157 views

Rational inscribed realization of the regular dodecahedron

While it is clear that the regular dodecahedron $D$ cannot be realized with all integer coordinates, it is easy to find a polytope, which is combinatorially equivalent (face lattice isomorphic) to $D$ ...
13
votes
0answers
431 views

Self-avoiding random walks that always turn

I am wondering if the statistics of self-avoiding random lattice-walks on $\mathbb{Z}^2$ that turn left or right at each step (i.e., they cannot continue the direction of the preceding step) have been ...
13
votes
0answers
3k views

Minimum tiling of a rectangle by squares

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes). Is there an efficient way to calculate this?
12
votes
0answers
469 views

Computer searches for the $g$-conjecture

McMullen's $g$-conjecture aims the classify possible $f$-vectors of simplicial $d$-spheres. The $g$-conjecture has been proven for polytopal spheres and for simplicial spheres of dimension $d < 5$. ...
12
votes
0answers
347 views

Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?

After reading these very interesting questions, I came up with another one: Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
12
votes
0answers
494 views

Reciprocity (Ehrhart-style) for real polytopes?

Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices? In other words, given any ...
11
votes
0answers
186 views

Euclidean realizations of a configuration of $27$ points and $45$ lines

Let $GQ(2,4)$ denote the abstract configuration (=incidence structure) consisting of $27$ points and $45$ lines, with $3$ points on leach line and $5$ lines through each point, which can be described ...
10
votes
0answers
184 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 ...
10
votes
0answers
124 views

A combinatorial proof of the Harrow--Kolla--Schulman theorem

Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$. For integers $0 \leq k \leq n$, define a ...
10
votes
0answers
235 views

Looking for method to generalize parity argument for Klein's Theorem (Happy Ending Problem)

The famous "Happy Ending Problem" for quadrilaterals states: Theorem Given a set of five points in the general position on the plane, there exists a subset of 4 which form the vertices of a convex ...
10
votes
0answers
280 views

Determining convexity of a polygon from its Fourier coefficients

Consider an $n$-sided polygonal curve in the plane, represented by an ordered set of points $(x_0, x_1, \ldots, x_{n-1})$; line segments connect consecutive points and also $x_{n-1}$ to $x_0$. It is ...
9
votes
0answers
174 views

Visibility in a growing orchard

This is a variant on Polya's orchard problem.1,2 Suppose trees are planted randomly in the plane. The question is: How many trees are visible from the origin as their radii grow? More precisely, ...
9
votes
0answers
273 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 ...
9
votes
0answers
137 views

Interactions between pseudoline arrangements and braid groups?

It is common to represent pseudoline arrangements as wiring diagrams:                     Fig. from: "Hamiltonicity and colorings of arrangement ...
9
votes
0answers
187 views

Herding sheep in a polygon

Imagine sheep fill a simple (simply connected) polygon $P$, except at one vertex $x$ there is no sheep. One convex vertex $g$ of $P$ is a gate through which the sheep should pass. A herding dog sits ...
9
votes
0answers
152 views

How many components are there in the space of “generic” planar N-gons? (Mnev's revenge)

Call an ordered $N$-tuple of points in the Euclidean plane ${\mathbb R} ^2$ "in general position" if no three points of the points in the set are collinear. As a function of $N$ how many components ...
9
votes
0answers
281 views

Neighborly family of coins

Here is a puzzle: Find 5 identical coins. Can you arrange them so that every coin is touching every other coin? The solution is here. The hint is: use the third dimension. My questions are ...
9
votes
0answers
233 views

Randomly placing nonoverlapping unit cuboids

Suppose one places unit cuboids of dimension $d$ with min-corners uniformly distributed to lie in $[0,n]^d$, but with cuboid (strict) overlap forbidden. At some point, the region is "saturated," ...
9
votes
0answers
410 views

How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

Title question description: Select two lattices $\Lambda_1$ and $\Lambda_2$ (here a lattice=additive free abelian group without accumulation points) of maximal rank two in the real plane. We normalize ...
8
votes
0answers
168 views

Does hereditary 2-coloring imply polychromatic 3-coloring for large edges?

For a hypergraph $\mathcal H=(V,\mathcal E)$, denote by $m_k$ the smallest number for which we can $k$-color any $X\subset V$ such that for any $E\in \mathcal E$ with $|E\cap X|\ge m_k$ all $k$ colors ...
8
votes
0answers
63 views

Minimizing union of overlapping rectangles

Believe it or not, this has something to do with making triangle-free graphs bipartite... We have a collection of $k$ axis parallel rectangles with side lengths $(a_i,b_i)$. We want to arrange them (...
8
votes
0answers
87 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 ...
8
votes
0answers
160 views

Which -icial sets produce the “standard” representations of symmetric groups?

Suppose you have a system of cell complexes (say, even convex polyhedra) $(P_n)_{n\geqslant0}$ which occur as faces of each other and are used to define the corresponding notion of "$P_*$-set". So ...
8
votes
0answers
181 views

Is the equidissection spectrum closed under addition?

If a polygon can be cut into $m$ as well as into $n$ triangular pieces of equal area, can it also be cut into $m+n$ triangles of equal area? (I'm editing after realizing that my conjecture that a ...
8
votes
0answers
1k views

Interpolating points with minimum curvature constraint

I have $n$ points $p_i$ strictly interior to a rectangle $R$, and I would like to connect them with a curve $C$ whose curvature is as low as possible. Let $\kappa_\max(C)$ be the sharpest (largest ...
8
votes
0answers
485 views

Maximal set on hypersphere that does not contain pairs of orthogonal vectors

Let R be a region on a hypersphere. Each point A of the hypersphere is associated with a vector pointing to A and with origin at the centre of the hypersphere. So let me identify each point with a ...
8
votes
0answers
324 views

Coloring toroidal polyhedra with convex faces?

Consider a toroidal polyhedron, which is a topological torus, in which all faces are planar, two faces meet in at most an edge, and adjacent faces are not coplanar. The Szilassi polyhedron has 7 non-...
8
votes
0answers
649 views

An Ex functor for the contravariant homotopy structure

I'm going to slack on the background and get to the point: Is there a good notion of an $Sd/Ex$ adjunction for $sSet/S$ equipped with the contravariant model structure (cofibrations are monomorphisms ...
8
votes
0answers
561 views

Historical and terminological questions about Dan Kan's Ex functor and its relation to the classical case of simplicial complexes

Recall that we may define a functor $\xi:\Delta\to \operatorname{Poset}$ sending a simplex $[n]$ to the set of monotone injections $[k]\hookrightarrow [n]$ for $k\geq 0$ (effectively, $k\leq n$ as ...
7
votes
0answers
35 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 ...
7
votes
0answers
192 views

Stabbing disks in space, or: Galactic alignment

I have a collection of $n$ unit-radius disks in $\mathbb{R}^3$, whose centers are random within a sphere of radius $R>1$, and which are each oriented randomly. I'd like to find a line $L$ that ...
7
votes
0answers
118 views

When are two pregeometries equivalent?

Some model theorists / combinatorial geometers like to think about pregeometries (matroids with a weak finiteness condition) associated to first-order theories. But the usual way of constructing a ...
7
votes
0answers
137 views

distance distributions on a hypersphere?

Fix a real number $0\leq t\leq 1$ and an integer $n>1$. Let $\mathbb{S}^{n-1}\subset\mathbb{R}^n$ denote the unit hypersphere. Define $$d_N(n;t):=\max\sum_{i<j}\Vert P_i-P_j\Vert_2^t$$ where ...
7
votes
0answers
113 views

Points on $k$ Circles

Let $k$ be a fixed positive integer. We want to find the minimum number $f(k)$, such that for a set of finite points in the plane, if any $f(k)$ of them are on $k$ circles, then all of them are on $k$ ...