All Questions
Tagged with mg.metric-geometry discrete-geometry
671 questions
6
votes
1
answer
508
views
How many triangulations of a regular octahedron are there, without introducing new vertices?
It is easy to find three triangulations, each consisting of four tetrahedra. Are there more?
- 61
11
votes
2
answers
455
views
Dodecahedral rolling distance
Let a dodecahedron sit on the plane,
with one face's vertices on an origin-centered unit circle.
Fix the orientation so that the edge whose indices are $(1,2)$ is horizontal.
For any $p \in \mathbb{R}...
- 151k
7
votes
0
answers
209
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 ...
- 151k
9
votes
3
answers
1k
views
What rectangles can a set of rectangles tile?
(I asked this question first on math.stackexchange, but did not get any responses so I thought I would try here.)
If we have a set of $p_i \times q_i$ rectangles ($p_i, q_i \in \mathbf{N}$), which $m \...
- 431
22
votes
3
answers
1k
views
Equilaterally triangulated surfaces with prescribed boundary
There is a problem in Richard Kenyon's list (Wayback Machine) which I would like to post here, because although I have thought about it from time to time, I have not been able to make the slightest ...
- 7,169
17
votes
5
answers
883
views
Rigidity of convex polyhedrons in $\mathbb R^3$ with faces removed
Take a convex polyhedron $P$ in $\mathbb R^3$ and remove all the faces, i.e. leave only the edges. Call this graph $E$. Let us now try to continuously deform $E$ in $\mathbb R^3$ so that all the edges ...
- 14.3k
4
votes
1
answer
124
views
Convex caps with prescribed edges and curvature
Let $G$ be the edge graph of a convex subdivision of a convex polygon $P$ in the plane. I would like to construct a convex polyhedral cap $C$ (with zero boundary values) over $P$ whose edges project ...
- 7,169
3
votes
1
answer
472
views
3D discrete curves geometry: method to order points in a same "general" ordering
I have a collection of 3D discrete curves $\{C_i\}$, each with a different number of points $N_i$:
$$ C_i = [p^i_0, p^i_1, ..., p^i_{N_i}] \text{ with } p^i_k=[x^i_k, y^i_k, z^i_k] \text{ i.e. } C_i \...
- 131
9
votes
0
answers
237
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 ...
- 151k
30
votes
5
answers
16k
views
How to check if a box fits in a box?
How could I calculate if a rectangular cuboid fits in an other rectangular cuboid, it may rotate or be placed in any way inside the bigger one.
For example would, (650,220,55) fit in (590,290,160), ...
- 429
10
votes
3
answers
537
views
Perimeter-halving center of a convex shape
Let $P$ be a convex polygon (or any convex body in $\mathbb{R}^2$)
with perimeter of length $1$. Call a chord $c$ of $P$ perimeter-halving
if half the perimeter lies to one side of $c$
(and so half to ...
- 151k
4
votes
0
answers
153
views
Perimeters of nested convex spherical polygons
I seek a reference—not a proof—that if $P_1$ and $P_2$
are two convex polygons on a sphere composed of geodesic segments,
contained in a hemisphere, and
$P_1 \subseteq P_2$, then the ...
- 151k
5
votes
1
answer
188
views
Transport tubes in a sphere
Let $S$ be a unit-radius sphere in $\mathbb{R}^3$.
Q0. Where should one place $3$ disjoint lines intersecting $S$ to minimize the maximum distance between
any two points in $S$, where distance is ...
- 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
16
votes
2
answers
466
views
Does a certain points and lines configuration exist?
For which $n$ we may mark $n$ red and $n$ blue points on the Euclidean plane, not all on a line, so that any line which passes through two points of different colour contains another point?
For $n=...
- 109k
4
votes
1
answer
263
views
Knotted TSP tours in 3D?
In the plane, the Euclidean TSP tour never crosses itself—it is always a simple polygon.
I am wondering if there is a similar constraint for the Euclidean TSP tour
of points in $\mathbb{R}^3$.
...
- 151k
7
votes
3
answers
2k
views
Partitioning a rectangle into different isosceles triangles
After all the discussion raised by this old question, I am wondering about a somewhat complementary one:
For any given rectangle, does there exist a finite set of pairwise different isosceles ...
- 13.4k
2
votes
1
answer
153
views
Bounding number of $k$-nearest neighbor sets in $\mathbb{R}^d$
Suppose that $\mathcal{X} \subseteq \mathbb{R}^d$ is compact.
Let there be $n$ distinct points $X = \{ x_1,...,x_n \} \subseteq \mathcal{X}$ and $k = \lfloor n^\alpha \rfloor$ where $0 < \alpha &...
- 23
33
votes
3
answers
5k
views
Do bubbles between plates approximate Voronoi diagrams?
For example, soap bubbles:
Image from UPenn:
"A 2-dimensional foam of wet soap bubbles squashed between glass plates, after 10 hours ...
- 151k
6
votes
0
answers
191
views
Cut locus on a hypercube
Inspired by the question, "Shortest path connecting two opposite points on a cube":
Q. What does the cut locus with respect to one corner of a hypercube
in $\mathbb{R}^d$ look like?
"The cut ...
- 151k
38
votes
7
answers
5k
views
Shortest path connecting two opposite points on a cube
Is it true, that a path connecting two opposite points (i.e. such that the segment joining them passes through the centre of mass of the cube) on the surface of the $d$-dimensional unit cube (with $d&...
- 1,431
4
votes
1
answer
422
views
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
For $k = 2$ the answer is obvious since we can always place circles so that every one of them ...
- 63
7
votes
0
answers
187
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 ...
- 43.2k
6
votes
2
answers
424
views
A class of tilings with amazing visual qualities
For more examples please see my related question on MSE:
Interesting tiling with a lot of symmetrical shapes
This is achieved by rotation of square grid over itself by atan(3/4).
Resulting ...
- 161
3
votes
1
answer
295
views
Monotone polygons (and polyhedra) with respect to a point
Dear mathoverflow community,
working on a visualization project I encountered a geometric problem, which I have not yet heard about and am interested in solving algorithmically. However a mere hint ...
- 31
10
votes
2
answers
387
views
What is Kept Fixed for Flexible Spheres
For background to this question much recent exciting related things, see this videotaped lecture by Alexander Gaifullin.
Consider a triangulation $K$ of a two-dimensional sphere and consider maps ...
- 24.7k
7
votes
1
answer
318
views
Finding a short path using $(0.99n)!$ permutations
Suppose I have $n$ points $x_1,\dots,x_n$ that are all independent uniform samples in the unit square, and I'd like to find a short path (in terms of Euclidean length) that touches all of them (a ...
- 4,049
3
votes
2
answers
202
views
Existence of lattices whose circles have bounded number of points
For any plane lattice $\Lambda= \{ mA+nB: m,n \in \mathbb Z \}$, with $A,B$ linearly independent vectors in $\mathbb R^2$, we define the set of the circles in $\Lambda$ as
$$\mathcal K(\Lambda) = \...
- 315
9
votes
2
answers
598
views
Dissecting Ramanujan´s Cuboid: 1729 = 19 x 13 x 7
Consider the cuboid of dimensions 19 x 13 x 7 whose volume is 1729, the Hardy-Ramanujan number. What is the least number of smaller cuboids into which it can be dissected so that the resulting pieces ...
- 3,707
15
votes
2
answers
885
views
Lattice n-gons with ordered side lengths 1,2,3,...,n
Consider the octagon in the Cartesian plane with vertices at (0,0), (1,0), (1,2), (4,2), (4,6), (7,2), (7,8), and (0,8).
Are there other (infinitely many) polygons, such as this, lying entirely in the ...
- 3,707
4
votes
2
answers
207
views
Classification of symmetries of tilings in surfaces?
Is there a general study of the symmetries of tilings on surfaces?
Conway, Goodman-Strauss & Burgiel classified them on $\mathbb S^2, \mathbb R^2$ and $\mathbb H^2$, with their 'Magic Theorem'. ...
- 561
19
votes
1
answer
448
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 ...
- 148k
22
votes
1
answer
696
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$ ...
- 10.7k
12
votes
1
answer
614
views
Covering the unit sphere by open hemispheres
Suppose $H_1,\ldots,H_{2n}$ are open hemispheres which cover $S^{n-1}$ with the property that removing any one of them leaves $S^{n-1}$ uncovered. Is it necessarily the case that the hemispheres can ...
- 219
21
votes
2
answers
1k
views
On convergence of convex bodies
Let $K\subset \mathbb{R}^n$ be a compact convex set of full dimension. Assume that $0\in \partial K$.
Question 1. Is it true that there exists $\varepsilon_0>0$ such that for any $0<\...
- 21.8k
2
votes
1
answer
189
views
What is the maximal diameter of a cell in a particular partition of the simplex?
Consider a standard simplex with points $(p_1, \dots, p_n)$, $p_i \ge 0$, and $\sum_i p_i = 1$. Fix a set $\{q_k\}_{k=1}^K$ with $0\leq q_k \leq \infty$ and $i,j\in\{1, \dots, n\}$. Partition it via ...
- 23
10
votes
1
answer
277
views
Optimization of points on a plane
Suppose we have $n$ points on a plane. Let $D$ be the sum of the squares of all the pairwise distances between the points. Let $A$ be the area of the convex hull. What is the minimum possible value of ...
- 1,129
0
votes
0
answers
89
views
What is the minimal number of lines needed to partition a simplex into cells of diameter at most $\epsilon$?
I am studying a problem that requires me to partition the simplex into cells using a particular family of hyperplanes. For concreteness, consider the 2-simplex. I would like to construct lines ...
- 23
5
votes
0
answers
135
views
What is the maximal convex hull in $\mathbb R^3$ of a tree with fixed total length?
Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the ...
- 13.4k
7
votes
1
answer
209
views
Are the primary parallelotopes classified? (equivalently, Voronoi cells of lattices)
A primary parallelohedron is a polyhedron that can fill space with infinite translated copies.
It is known (e.g., Coxeter, H. S. M. Regular Polytopes, 3rd ed. New York: Dover, pp. 29-30, 1973; or, ...
- 1,441
0
votes
1
answer
71
views
A bound on the Haussdorff distance
Let $X, Y \subset \mathbb{Z}^2$ be two discrete and bounded sets. Let $f_X$ be the Euclidean signed distance function of $X$ (similarly for $Y$) and $d_H(X,Y)$ the Euclidean Haussdorff distance ...
- 59
3
votes
1
answer
190
views
How many points are in such set with the same norm-2
Let $L=[a,b]\cap\mathbb{N}$ with $a,b\in\mathbb{N}$, let $D\in\mathbb{N}$, and let $C=L^D$. Then I would like to know how many points are there in $C$ with the same given norm-2 $d$. I.e., I'm looking ...
3
votes
1
answer
205
views
How to show it is contained in a convex hull?
There are $(d+1)f$ points (denote the set of all points as $S$) in $\mathbb{R}^d$, that can be divide into $d+1$ disjoint sets $F_1,...,F_{d+1}$, each set of size $f$. If we have
$$
\mathcal{H}(F_i)\...
- 43
5
votes
1
answer
303
views
Intersection of rotating regular polygons
This question has a recreational flavor, but may not be
entirely uninteresting.
Let $P_k$ be a unit-radius regular polygon of $k$ sides,
and $P_n$ a unit-radius regular polygon of $n \ge k$ sides.
...
- 151k
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
34
votes
1
answer
3k
views
Tiling a square with rectangles
Is it possible to completely tile a square with different rectangles of integer sides but all with the same area?
The original problem, not requiring integer sides for rectangles, was proposed by Joe ...
- 3,707
8
votes
1
answer
2k
views
Lattice points on the boundary of an ellipse
How many points of the integer lattice ${\mathbb Z}^2$ can an axis-parallel ellipse of radius $r$ contain on its boundary? (that is, we consider ${\mathbb Z}^2$ as lying in ${\mathbb R}^2$). ...
- 1,072
7
votes
1
answer
153
views
Above/below directed graph on cells of arrangement of lines
This question concerns the structure of a directed graph
built on the cells of an arrangement of lines.
My basic question is whether this graph has been
studied before, perhaps in another guise. I ...
- 151k
2
votes
1
answer
248
views
Choosing the weights of a Voronoi diagram -- is this function always the gradient of another function?
This question is related to the earlier question Weighted area of a Voronoi cell . As in that question, let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,...
- 4,049
4
votes
2
answers
162
views
Basic question about discrete minimal surfaces
Let $P$ be a convex polygon with $n > 3$ vertices $v_1, \ldots, v_n \in \mathbb{R}^2$, let $x$ be a point in the interior of $P$, and let $u$ be a function with prescribed values at the vertices of ...
- 133