All Questions
Tagged with reference-request discrete-geometry
174 questions
7
votes
3
answers
377
views
Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$
Let $P_n$ be a "random convex polyhedron" in $\mathbb{R}^3$ of $n$ vertices, where "random" could follow any one
of a number of models:
(1) the convex hull of $n$ points randomly and uniformly ...
- 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
0
answers
189
views
Slices of Simplices that are Simplices, Reference?
I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere.
Let $A$ be an $l\times n$ matrix with ...
- 41
11
votes
3
answers
665
views
Limit shape for fixed-perimeter lattice polygons
Let $P$ be a simple polygon defined by $n$ unit-length segments
connecting lattice points of $\mathbb{Z}^2$.
I have two operations that preserve the perimeter of $P$.
The first is the "pop" of a ...
- 151k
16
votes
4
answers
2k
views
Point sets in Euclidean space with a small number of distinct distances
It is well known and not hard to prove that the regular simplex in n-dimensions is the only way to place n+1 points so that the distance between distinct pairs of points is always the same. My general ...
- 1,314
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
13
votes
3
answers
1k
views
Random Reidemeister moves to unknot
Suppose one has a link diagram of the unknot, and applies random Reidemeister moves
until the unknot is reached.
Surely it requires an exponential number of moves, exponential in, say, the crossing ...
- 151k
29
votes
3
answers
2k
views
Growing random trees on a lattice $\rightarrow$ Voronoi diagrams
Imagine growing trees from $k$ seeds on a square $n \times n$ region
of $\mathbb{Z}^2$.
At each step, a unit-length edge $e$ between two points of
$\mathbb{Z}^2$ is added.
The edge $e$ is chosen ...
- 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
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
12
votes
2
answers
1k
views
Helly theorem + Nerve
Consider nerve $\mathcal N$ of a finite set of convex sets in $\mathbb R^n$.
Helly theorem says that $\mathcal N$ is completely determined by its $n$-skeleton, say $\mathcal N_n$.
It seems that not ...
- 1,785
15
votes
2
answers
737
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 ...
- 881
10
votes
2
answers
930
views
What is determined by the combinatorics of the shadows of a convex polyhedron?
Define the shadow of a convex polyhedron $P$ in direction $u$
to be the orthogonal projection of $P$ onto a plane whose normal is $u$.
The shadow is a convex $k$-gon.
I am wondering to what degree $P$ ...
- 151k
8
votes
0
answers
358
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-...
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
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
24
votes
2
answers
1k
views
A geometric Ramsey problem
The following problem seems like one to which the answer could well be known: if so, I'd be interested to have a reference.
How large does n have to be such that among any n points in the plane you ...
- 29k
21
votes
2
answers
1k
views
Forbidden mirror sequences
Let $\cal{M}$ be a finite collection of two-sided mirrors,
each an open unit-length segment in $\mathbb{R^2}$,
and such that the segments when closed are disjoint.
A ray of light that reflects off the ...
- 151k
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
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
11
votes
2
answers
1k
views
Which (semi)regular polyhedra are combinations of two others?
The convex combination of convex polytopes is a convex polytope.
An example in $\mathbb{R}^2$ is that a regular octagon
can be obtained as $\frac{1}{2} S + \frac{1}{2} S'$,
where $S$ is a square and $...
- 151k
3
votes
0
answers
142
views
Dimension of convex arrangements for hypergraphs
Suppose you have a hypergraph H on n vertices. Let d be the smallest integer such that we can find an arrangement A of convex subsets in Rd so that H represent the intersections of sets in A.
Has ...
- 4,586
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
5
votes
2
answers
333
views
Characterization of combinatorial manifolds in terms of links
I need to reference the following result. Do you know a good source?
The following conditions on an $n$-dimensional simplicial complex $S$ are equivalent:
a) $S$ is an $n$ manifold;
b) The link of ...
- 5,019