Questions tagged [discrete-geometry]
Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.
1,819
questions
15
votes
3
answers
1k
views
Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.
Is the following fact true?
Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k \...
15
votes
2
answers
568
views
Spearing rolling hula hoops
Or: Stabbing rolling disks.
Imagine there are $n$ unit-diameter disks rolling between $x=0$ and $x=d$,
reflecting off either end.
The disk centers start at a random location within $[\frac{1}{2}, d-\...
15
votes
3
answers
2k
views
Combinatorial analogues of curvature
There appear to be many "combinatorial" definitions of curvature as applied to finite simplicial (or regular CW) complexes. For instance, we have the ideas of Cheeger, Muller and Schrader, ...
15
votes
1
answer
927
views
Are there irregular tilings by L-polyominoes?
I wonder if one can tile the plane with an order-$n$ L-polyomino
in a fundamentally irregular manner.
I seek help in defining what should constitute "irregular."
An L-polyomino of order $n \...
15
votes
1
answer
1k
views
Conjecture: If equal size circular coins are in a convex polygonal frame, with each coin touching exactly one edge, then all the coins can move
Earlier I conjectured that if circular coins of any sizes are in a convex polygonal frame, with each coin touching exactly one edge, then all the coins can move. A counter-example using coins of ...
15
votes
2
answers
718
views
Tiling survey that updates "Tilings and patterns"?
Can anyone suggest a survey (or surveys) that provides an update to Tilings and patterns by Grunbaum and Shepard? If there's a more recent book, that would be fantastic, but I don't see one.
I am ...
15
votes
1
answer
301
views
Annihilating random walkers
Suppose there are several walkers moving randomly on $\mathbb{Z}^2$,
each taking a $(\pm 1,\pm 1)$ step at each time unit.
Whenever two walkers move to the same point, they
annihilate one another. ...
15
votes
1
answer
631
views
Smallest regular simplex containing the unit cube in $R^n$
What is the length $e_n$ of the edge of the smallest $n$-dimensional regular simplex $S_n$ containing the $n$-dimensional unit cube $Q_n$?
In particular, is there $n$ such that $e_n<\sqrt{2}(n+1-\...
15
votes
2
answers
767
views
Three squares in a rectangle
One of my colleagues gave me the following problem about 15 years ago:
Given three squares inside a 1 by 2 rectangle, with no two squares overlapping, prove that the sum of side lengths is at most 2. (...
15
votes
1
answer
371
views
separating points in $\mathbb{R}^d$ by minimal number of planes
Given $n$ points of general position in $\mathbb{R}^d$ (say, $n>d$ and no $d+1$ lie in a hyperplane.) We want to draw $k$ hyperplanes not passing through those points so that they all are in ...
15
votes
1
answer
810
views
Ratio of circumscribed/inscribed $(n{-}1)$-gons
As a discrete analog of the MO question,
"Löwner-John Ellipsoid: incribed and circumscribed,"
I've been wondering what might be the maximum ratio
of this quantity?
Let $P$ be a convex ...
15
votes
1
answer
2k
views
Ping-pong relief map of a given function z=f(x,y)
I have an idea to design a type of
Galton's Board
to "draw" a relief map of a given two-dimensional function $z=f(x,y)$.
A typical Galton's Board drops, say, ping-pong balls through a series
of evenly ...
15
votes
0
answers
474
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
0
answers
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
7
answers
2k
views
Finite set of non-collinear points on plane with every point having ≥ 3 equidistant neighbors? [closed]
Does there exist a finite set of points on the Euclidean plane, such that:
No 3 points are collinear, and
Every one of the points has (at least) three other points in the set at the same distance ...
14
votes
3
answers
958
views
Can a tangle of arcs interlock?
Can a (finite) collection of disjoint circle arcs in $\mathbb{R}^3$ be interlocked in the sense in that they cannot be separated, i.e. each moved arbitrarily far from one another while remaining ...
14
votes
4
answers
445
views
Smallest containing simplex
Let $V_n$ be the least real number such that for every convex subset of $\mathbb{R}^n$ with hypervolume $1$ there is a containing simplex with hypervolume $V_n$.
What is known about $V_n$? Is there a ...
14
votes
4
answers
1k
views
A notion of 2-dimensional tree
Summary: This post has got rather long after the discussion. The main still open Questions are 5 & 6 below. There is work in progress, and I'll post an update at some point.
A tree is a connected ...
14
votes
2
answers
874
views
Sets of evenly distributed points in the Euclidean plane
Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection
with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?
If the answer is yes, can $P$...
14
votes
2
answers
656
views
How to characterize the regularity of a polygon?
In my research, I've recently started to play with Voronoi tessellations. I currently have a Python code that creates the tessellation and I am trying to color the polygonal regions according to their ...
14
votes
2
answers
533
views
Are all well behaved "mean" functions on $\mathbb{R}^+$ equivalent?
Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties:
$M(a,a)=a\qquad$ (identity)
$M(a,b)=M(b,a)\qquad$ (commutativity).
and possibly
$M(M(a,b),M(a,c))=...
14
votes
1
answer
802
views
The geometry of crinkled aluminum foil
I wonder if the geometry of crinkled aluminum foil has been studied?
The above is a photo of foil I flattened to reuse.
It might be ...
14
votes
1
answer
596
views
Which sets of lattice points have rational generating functions?
Let $P$ be a subset of $\mathbb N^d$ (or of some normal pointed affine semigroup), and suppose that $f:=\sum_{p\in P}\ t^p\in\mathbb Z[[t_1,\ldots,t_d]]$ is a rational function. What can be said ...
14
votes
3
answers
1k
views
A curious generalization of Helly's theorem
Here is a curious conjectural extension of Helly's theorem.
It may follow (if true) from a useful theorem of the kind asked in this MO question:
Conjecture: Let ${\cal F}=P_1,P_2,\dots,P_m$ be a ...
14
votes
1
answer
272
views
How many distances are required to calculate all distances among $n$ points in the Euclidean plane?
I want to know all the pairwise distances between points $P_1,P_2,\ldots,P_n$ in the Euclidean plane (or equivalently, I want to reconstruct the set of points up to congruence). Let's say I have an ...
14
votes
3
answers
2k
views
Optimal wireframe sphere
Suppose you have a length $L$ of metal pipe at your disposal,
and you would like to build a wireframe unit-radius sphere,
by bending, cutting, and welding the pipe into a connected structure $F$.
Your ...
14
votes
1
answer
912
views
Partitioning the vertices of an n-cube with random hyperplane cuts
An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry.
It is an old chestnut of a ...
14
votes
1
answer
559
views
Sheaves in combinatorics and discrete geometry
I am looking for examples for the application of sheaves, sheaf-like constructions or the (co)homology of sheaves to problems in combinatorics and discrete geometry.
For example given a poset $(P,\...
14
votes
1
answer
361
views
Exotic line arrangements
I would like to discuss the following problem. Hopefully, you will suggest to me some ideas and bibliography.
At first I will provide some basic definitions to set up the notation.
Let us consider ...
14
votes
1
answer
645
views
Is the Ford disk packing optimal?
Given two unit-diameter disks tangent to a given line and to each other, determining a region bounded by two circular arcs and a line segment, is the Ford disk packing of that region the unique ...
14
votes
0
answers
259
views
Regular $n$-gon with diagonals: bounds on area of largest cell?
Consider a regular $n$-gon of side length $1$ with diagonals. Here is an example with $n=11$ (from geogebra applet).
I've been trying to find, in terms of $n$, bounds on the area of the largest cell, ...
14
votes
0
answers
477
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 ...
14
votes
0
answers
4k
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?
13
votes
5
answers
1k
views
Packing obtuse vectors in $\mathbb{R}^d$
I came across this attractive theorem:
Theorem. In $\mathbb{R}^d$, there can be at most $d+1$ vectors that
form an obtuse angle with one another.
This was proved1 as a corollary of a lemma about ...
13
votes
3
answers
1k
views
(non-)existence of the aperiodic monotile
The aperiodic monotile problem asks whether there exists a single tile that every tiling of the plane made with it results non-periodic. What is known about this problem? If this tile exists, how can ...
13
votes
3
answers
819
views
What fraction of n-point sets in the unit ball have diameter smaller than 1?
This question is inspired by a recent talk by Matt Kahle on random geometric complexes.
Some simple notation: let $\mathcal{B} \subset \mathbb{R}^d$ be the unit ball in $d$-dimensional Euclidean ...
13
votes
2
answers
3k
views
How many squares can be formed by using n points?
How many squares can be formed by using n points on a 3 dimensional space?
Like using 4 points, there is 1 square be formed
Using 5 points, still 1 square
Using 6 points, 3 squares can be formed
13
votes
2
answers
3k
views
How many vertices/edges/faces at most for a convex polyhedron that tiles space?
I wonder if this problem has already been examined before:
Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have?
...
13
votes
2
answers
3k
views
Subdivision of triangles into congruent triangles
Recently some old notes of mine have gotten me to thinking about the problem of subdividing a triangle into $N$ smaller triangles, all congruent to one another. A little thought shows the following ...
13
votes
1
answer
296
views
Is every finite $d$-dimensional matrix group generated by $d$ elements?
The question is in the title. If $\Gamma\subset\mathrm{GL}(\Bbb R^d)$ is a finite matrix group, can it be generated by (at most) $d$ elements?
I suspect that this hope is too naive, but I have no ...
13
votes
3
answers
414
views
Maximal distance between $2d+1$ points on the $(d-1)$-sphere
If one arranges $2d$ points on the sphere $\mathbf S^{d-1}\subset\Bbb R^d$ at the vertices of the crosspolytope, then one can achieve a minimal spherical distance of $\pi/2$ between any two points, ...
13
votes
3
answers
658
views
Are there Monohedra with odd numbers of faces?
A monohedron is a convex polyhedron with all faces mutually congruent but with no other symmetry necessarily needed. So obviously, this is a wide class of polyhedra that includes the Platonic solids ...
13
votes
2
answers
815
views
Acute triangulation
Assume that $S$ is a finite 2-dimensional simplicial complex equipped with a metric $d$
such that each triangle is isometric to a plane triangle (so $(S,d)$ is a polyhedral space).
Is it possible ...
13
votes
2
answers
513
views
Double kissing problem
Consider two touching unit balls which will be called central balls. What is the maximum number $k$ of non-overlapping unit balls so that each ball touches as least one of two central balls?
An easy ...
13
votes
2
answers
465
views
When does a set of collinearity conditions imply collinearity of all of the points?
Suppose we have a set of $n$ points $\{X_1,X_2,\dots,X_n\}$ in the real plane and $\mathcal{A}$ a family of subsets of $\{1,\dots,n\}$.
By a "set of collinearity conditions for $\mathcal{A}$" we mean ...
13
votes
2
answers
1k
views
Average degree of contact graph for balls in a box
Imagine you dump congruent, hard, frictionless balls in a box,
letting gravity compress the balls into a stable configuration
(I believe such configurations are called
jammed.)
Assume the box ...
13
votes
1
answer
3k
views
What nets fold to polyhedra?
There is a classic (and open) problem asking whether every polyhedron can be unfolded to give a non-overlapping net. The converse problem has been studied asking which polygons can be folded in some ...
13
votes
3
answers
1k
views
When are Ehrhart functions of compact convex sets polynomials?
Given a lattice $L$ and a subset $P\subset \mathbb R^d$, we define for each positive integer $t$ $$f_P(L,t)=|(tP\cap L)|$$ the number of lattice points in $tP$. Let's say $P$ is nice if $f_P(L,t)$ is ...
13
votes
3
answers
357
views
Intersecting cylinders around a sphere
Intersecting $n$ unit-radius cylinders, each with axis through the origin,
produces a shape circumscribed about a unit-radius sphere:
My question is:
For each $n$, which arrangement of cylinders ...
13
votes
2
answers
859
views
Discrete Morse function from smooth one
Suppose I have a smooth manifold $M$ and a smooth Morse function $f$ on $M$. Is there a standard way to replace $M$ with a cell complex and $f$ with a discrete Morse function such the resulting ...