All Questions
Tagged with discrete-geometry reference-request
39 questions
8
votes
4
answers
530
views
Inside-out polygonal dissections
A dissection of a polygon $P$
is a partition of $P$ into a finite number of pieces, which can then be rearranged
(via planar translations and rotations) and joined (without overlap) to form a new ...
- 151k
34
votes
6
answers
8k
views
Covering a unit ball with balls half the radius
This is a direct (and obvious) generalization of the recent MO question, "Covering disks with smaller disks":
How many balls of radius $\frac{1}{2}$ are needed to cover completely a ball of ...
- 151k
52
votes
5
answers
2k
views
Tetris-like falling sticky disks
Suppose unit-radius disks fall vertically from $y=+\infty$,
one by one, and create a random jumble of disks above the $x$-axis.
When a falling disk hits another, it stops and sticks there.
Otherwise, ...
- 151k
18
votes
2
answers
840
views
Reference to a conjecture on unit vectors in Euclidean space
I have heard that there exists the following conjecture (if I am not mistaken).
Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists another unit vector ...
- 21.8k
25
votes
1
answer
3k
views
Number of hypercube unfoldings
While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we ...
- 10.7k
24
votes
1
answer
2k
views
Building a genus-$n$ torus from cubes
I wonder if this has been studied:
What is the fewest number of unit cubes
from which one can build an $n$-toroid?
The cubes must be glued face-to-face,
and the boundary of the resulting object ...
- 151k
17
votes
1
answer
458
views
The sparsest planar net that captures every unit segment
Let $\cal C = \lbrace C_i \rbrace$ be a collection
of rectifiable curves in the plane with the property that
every unit-length segment meets at least one curve
in at least one point.
Call such a ...
- 151k
16
votes
1
answer
1k
views
Random polycube shapes
I am wondering if it is hopeless to obtain any firm results
on the following model of a "random polycube shape."
First, a polycube in $\mathbb{R}^3$
is a connected face-to-face gluing of unit cubes.
(...
- 151k
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 ...
- 151k
8
votes
1
answer
885
views
Maximal tetrahedra inscribed in ellipsoid
Pietro Majer quoted the theorem of Michel Chasles in his MO question,
"Convex curves with many inscribed triangles maximizing perimeter,"
which states that the triangles of maximum perimeter inscribed ...
- 151k
6
votes
4
answers
2k
views
Delaunay triangulations and convex hulls
This is a reference request.
I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...
4
votes
1
answer
493
views
Counting number of points on a lattice in a hypercube
Suppose I have a lattice $\Lambda \in \mathbb{R}^n$. Let $X_i >0$ for $i=1,..,n$. I am interested in some references regarding counting number of points of $\Lambda$ inside $[-X_1, X_1] \times \...
- 3,625
3
votes
1
answer
394
views
Min Bend Orthogonal Knots
I am seeking literature on 3D orthogonal drawings of knots,
especially minimum bend drawings.
An orthogonal drawing employs segments parallel to the axes of
a Cartesian coordinate system.
A bend is a ...
- 151k
45
votes
1
answer
2k
views
Pach's "Animals": What if the genus is positive?
Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:
Can every animal—a topological ball in $\mathbb{R^3}$ composed of unit cubes glued face-to-face—be ...
- 151k
23
votes
1
answer
714
views
Covering the unit sphere in $\mathbf{R}^n$ with $2n$ congruent disks
Let $v_i$ be $2n$ points in $\mathbf{R}^n$, with equal distance $|v_i|$ from the origin. Suppose that the convex hull of these points contains the unit ball. Is it known that $|v_i|\geq\sqrt{n}$? ...
- 7,194
22
votes
1
answer
970
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 ...
- 528
21
votes
5
answers
1k
views
Is a rhombus rigid on a sphere or torus? And generalizations
If a rectangle is formed from rigid bars for edges and joints
at vertices, then it is flexible in the plane: it can flex
to a parallelogram.
On any smooth surface with a metric, one can define a ...
- 151k
17
votes
1
answer
1k
views
The optimal constant in Vitali covering lemma
Let me restate Vitali covering lemma.
Let $\{B_i\}_{i\in F}$ be a finite collection of balls in the $\mathbb{R}^n$. Then there is $S\subset F$ such that the balls $\{B_i\}_{i\in S}$ are disjoint and
...
- 293
16
votes
6
answers
2k
views
Optimal pebble-packing shape
Suppose you throw many ($n$) congruent convex bodies (in $\mathbb{R}^3$) of unit volume (or of unit area in $\mathbb{R}^2$) into a large container, and shake it until little else changes.
Q. ...
- 151k
15
votes
0
answers
477
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 ...
- 151k
14
votes
1
answer
781
views
Perimeters of random-walk polygons
I have a random walk on $\mathbb{Z}^2$ that takes a step
with equal probability in the three directions that avoid
retracing the previous step.
The walk proceeds until it returns to a lattice point
...
- 151k
12
votes
2
answers
2k
views
Fold-and-cut problem in three dimensions
The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include ...
- 851
11
votes
1
answer
406
views
Thinnest 2-fold coverings of the plane by congruent convex shapes
It is an unsolved problem to determine the "thinnest" $2$-fold covering of
the plane by disks.
The $2$-fold coverage problem by disks is to find the minimum number of congruent
(unit-radius) disks ...
- 151k
11
votes
1
answer
607
views
Largest pair of homometric Golomb rulers?
A Golomb ruler is a set of $n$ integers that determines $\binom{n}{2}$ distinct differences.
Two sets are homometric if they determine the same (multiset) of differences.
For example,
$$\{0,1,4,10,12,...
- 151k
11
votes
3
answers
1k
views
Combinatorial distance between simplicial complexes
Let $K_1$ and $K_2$ be two simplicial complexes.
I am seeking a measure of the distance between $K_1$ and $K_2$ when
viewed as combinatorial objects.
What I have in mind is something like this.
...
- 151k
10
votes
1
answer
426
views
Complexity of the union of randomly rotated unit cubes
It is a remarkable fact that the union of congrent cubes
has only at most near-quadratic combinatorial complexity,
$O^*(n^2)$ for $n$ cubes, known to be almost tight.
This contrasts with the union of ...
- 151k
10
votes
2
answers
280
views
Monochromatic point sets in two-colored plane
Which are the configrations $P\subset \mathbb{R}^2$ of points, such that the following property holds:
Property M (for Monochromatic): Every two-coloring of $\mathbb{R}^2$ contains a monochromatic ...
- 10.7k
9
votes
1
answer
460
views
Connections between linear representations and permutation representations
A finite group $\Gamma$ might be represented by a linear transformation
$$\rho : \Gamma\to\mathrm{GL}(\Bbb R^d),$$
or by permutations
$$\phi :\Gamma\to\mathrm{Sym}(n).$$
Of course, latter ones can ...
- 13.6k
9
votes
4
answers
474
views
Minimum number of common edges of triangulations
Let $S$ and $T$ be two triangulations.
We define
$c(S,T)$ as the number of edges shared by $S$ and $T$.
With this, we can define
$f(n) = \min_{P} \min_{S,T} c(S,T)$.
Here the first minimum goes over ...
- 479
7
votes
1
answer
938
views
Which knots' stick numbers are twice their crossing numbers?
Looking at a table of minimum stick numbers for knots (table here),
it seems the known upper bound of $2 c(K)$ in terms of the knot crossing number $c(K)$
is realized by the trefoil $3_1$—it ...
- 151k
6
votes
2
answers
544
views
On circles and ellipses drawn on an infinite planar square lattice
Consider a plane with a square lattice formed by all points with both coordinates as integers. As can be easily seen, a simple parabola can be found that passes through infinitely many of the square ...
- 5,979
6
votes
2
answers
364
views
Triangles whose vertices and center have all the same color
A plane is colored with two colors. It's an easy exercise to prove that it's always possible to find an equilateral triangle whose vertices have all the same color.
Does anyone know any proof or ...
- 3,153
6
votes
1
answer
295
views
A conjecture (or theorem?) on unit vectors in a Euclidean space
I have heard (if I am not mistaken) that there exists the following conjecture (or theorem?).
Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists ...
- 21.8k
5
votes
2
answers
441
views
Touching-tetrahedra graphs
Have the graphs representable by touching tetrahedra been explored?
Let $\cal T$ be a collection of tetrahedra in $\mathbb{R}^3$
with pairwise disjoint interiors.
Define a graph $G_{\cal T}$ to have ...
- 151k
4
votes
1
answer
646
views
Combinatorial geodesics
[There has been a flaw in my definition - as Sergei and Andreas pointed out. I hope I could fix it.]
I want to understand how the concepts of directions, straight (or shortest) lines, and geodesics &...
- 9,720
4
votes
2
answers
425
views
Algorithm for Reconstructing Point Sites from a Voronoi Diagram
how can one construct a finite set of points in the euclidean plane from its Voronoi Diagram and, what is the complexity of the problem?
- 13.2k
3
votes
0
answers
135
views
Intersecting the unit n-cube and (n-1)-planes
(Is this a known problem?)
Question Let $\ 1<n\in\mathbb N.\ $ What is the greatest $(n-1)$-area
$\ S(n)\ $ of $\ L\cap I^n\ $ where $\ I^n\subseteq\mathbb R^n\ $ is the unit cube, and $\ L\ $ ...
- 4,786
3
votes
1
answer
1k
views
Regularity of Delaunay triangulation of a hypercube
First using a three dimensional unit cube as an example for the term "regularity", we can have two possible triangulations:
(A)
(B)
We say the lower triangulation is more "regular" than upper ...
- 339
3
votes
1
answer
159
views
Work on "Churning Polygons"
Background of this question is that I recently stumbled over the problem of deforming polygons in area-preserving way, i.e. modifying the angles between adjacent edges while preserving edge-lengths, ...
- 13.2k