All Questions
Tagged with mg.metric-geometry discrete-geometry
671 questions
24
votes
2
answers
754
views
Expected number of vertices of a hypercube slice -- is this new/interesting?
I am a (mostly) amateur mathematician, but my education and work have featured a lot of mathematics, and recently I bumped into a mathematical problem for which I can find no references, and I am ...
- 121
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 ...
- 2,581
14
votes
0
answers
479
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 ...
- 7,169
25
votes
3
answers
994
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose edges ...
- 32.1k
8
votes
1
answer
591
views
Polyhedra that combinatorially shadow a sequence
Let $P$ be a polyhedron in $\mathbb{R}^3$.
Say that $P$ combinatorially shadows a sequence of natural numbers $S$ if
there is a continuous rotation of $P$ such that its orthogonal-projection
shadows ...
- 4,713
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
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
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 ...
- 13k
10
votes
1
answer
465
views
Chord arrangement that avoids confining small or large disks
These two questions are two-dimensional variations on this recent MO question,
"Threading pinholes in the wall of cylinder to pass through an internal coordinate."
Noam Elkies suggested that even a 2D ...
- 151k
7
votes
3
answers
805
views
Wrapping a convex polyhedron with string
This is a meta-question, rather than a specific mathematical question.
I am seeking a mathematical definition that captures the following physical idea.
Suppose you have a convex polyhedron $P \...
- 18.6k
6
votes
2
answers
256
views
Form a $\mathbb{Z}^d$ lattice cycle from given lengths
Suppose you are given a list of integer lengths,
e.g.,
$(5,3,2,2,1,1,2,1,1)$.
The task is to decide if they can form a closed cycle
in $\mathbb{Z}^d$ by connecting segments of those
lengths in order, ...
- 151k
6
votes
2
answers
217
views
Untangling entwined rigid chains in 3-space
I am interested in exploring the degree of "tangledness"
of two rigid chains in space.
A polygonal chain is a simple (non-self-intersecting) path
of segments in
$\mathbb{R}^3$, viewed as a rigid body. ...
- 151k
14
votes
1
answer
819
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 ...
- 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
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
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
32
votes
5
answers
1k
views
Can every $\mathbb{Z}^2$ disk be pinball-reached?
Let every point of $\mathbb{Z}^2$ be surrounded by a mirrored disk of radius $r < \frac{1}{2}$,
except leave the origin $(0,0)$ unoccupied by a disk.
Q. Is it the case that every disk can be hit ...
- 151k
1
vote
0
answers
371
views
Simple development of simple curve on a cone
Let $\Lambda$ be a cone with apex $a$ and apex angle $\alpha$. Draw a simple (non-self-intersecting)
curve $C=(x,y)$ on $\Lambda$, and then develop it to a curve
$\overline{C}$ on a plane by rolling $...
- 151k
4
votes
1
answer
323
views
What properties does generalized Delaunay triangulation have?
Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...
- 4,713
5
votes
1
answer
383
views
cover and hide with squares
I am studying two numbers, related to squares, that can characterize a polygon P:
MinCoverNumber = the minimum number of axis-aligned squares required to exactly cover P (the covering squares may ...
- 151k
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 ...
- 151k
6
votes
3
answers
482
views
Herringbone partitions of regions and surfaces
Let $R \subset \mathbb{R}^2$ be a region of the plane bounded
by a Jordan curve. The boundary $\partial R$ could be a polygon,
or a smooth curve—there are variations depending upon boundary ...
- 4,713
2
votes
2
answers
345
views
packing disks tightly in the plane
Given a discrete point set $S$ in ${\bf R}^2$ with a specified base-point $p_0 \in S$, label the remaining points as $p_1, p_2, \dots$ in order of increasing distance from $p_0$ (with ties resolved ...
- 13.4k
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.6k
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 ...
- 151k
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
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
9
votes
3
answers
525
views
Mutually tangent ellipsoids in 3 space
I recently heard a claim that for any n, it is possible to arrange n ellipsoids in 3 space such that each pair of ellipsoids is kissing. Is this true, and if so, how?
Edit: By kissing, I mean that I ...
- 151k
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
10
votes
5
answers
960
views
Is this an instance of any existing convex pentagonal tilings?
Inspired by Wikipedia's article on pentagonal tiling, I made my own attempt.
I believe this belongs to the 4-tile lattice category, because it's composed of pentagons pointing towards 4 different ...
- 151k
6
votes
1
answer
767
views
Using mirrors to make a non-convex polygon visible from a fixed interior point
Take a point $A$ inside a non-convex polygon $P$. Is it always possible to place a finite set of mirrors given by straight segments (not necessarily along the boundary of $P$, any position inside $P$ ...
- 4,713
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&...
- 4,713
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 ...
- 4,786
15
votes
2
answers
2k
views
Partitioning a Rectangle into Congruent Isosceles Triangles
Is it possible to partition any rectangle into congruent isosceles triangles?
- 4,713
4
votes
1
answer
377
views
Discrete gradient ascent cycles
I am wondering what can be inferred when a discrete
gradient ascent algorithm gets stuck in a cycle.
Here is the situation.
A function $f(x,y)$ is defined over a range $[0,n]^2$,
and the algorithm ...
- 151k
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 &...
- 109k
1
vote
2
answers
1k
views
Is there always a parallelogram cross-section of parallelepiped contained in the smallest box
Let $M$ be a centered parallelepiped, the intersection of $M$ and any plane $P$ that passes through the origin is a parallelogram or hexagon. Each parallelogram or hexagon has a cubic box that is the ...
CommunityBot
- 1
8
votes
2
answers
2k
views
What's the name of this geometric mathematical modeling problem?
There is a right angle corner with width 1 in both directions. One wants to find the largest area shape which can pass through this corner.
I know that this is a famous problem, but what is it called?
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 ...
- 4,713
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 ...
- 13.6k
13
votes
1
answer
430
views
Detecting a hidden convex body with line probes
Imagine that, somewhere inside an origin-centered, unit-radius sphere
$S$ in $\mathbb{R}^3$,
sits a convex body $K$ of volume vol$(K)=\alpha (\frac{4}{3} \pi)$,
with $\alpha < 1$ the fraction of ...
- 151k
11
votes
1
answer
424
views
Needle probing for a convex body
Suppose there is an unknown closed convex body $K$ of
volume vol$(K) = V$ inside the
unit cube $[-\frac{1}{2}, \frac{1}{2}]^d$ in $\mathbb{R}^d$.
You are permitted to probe with a (one-dimensional)
...
- 151k
11
votes
1
answer
712
views
Polygons uniquely inducing arrangements
A beautiful, relatively recent result is that,
Every simple arrangement $\cal{A}$ of $n$ lines in the plane is induced by a simple $n$-gon $P$.
In a simple arrangement, every pair of lines intersect ...
CommunityBot
- 1
6
votes
2
answers
381
views
Lattice-cube minimal blocking sets
Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with
each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$.
Define a blocking set for a lattice cube to be a set of points
in ...
- 151k
17
votes
4
answers
823
views
Sweep-segment bot: Will this random walk sweep the plane?
This model is inspired by the random behavior of the
Roomba sweeping robot.
Let a unit segment $ab$ in the plane be placed
initially with $a=(0,0)$ and $b=(1,0)$.
The segment is first rotated a ...
- 151k
1
vote
1
answer
226
views
Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier
Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$.
Q1. What is the least time complexity
possible/known for recreating the
...
- 151k
3
votes
1
answer
292
views
Existence of Simple Closed Straightest Geodesics
There are at least three distinct simple closed quasigeodesics on convex polyhedra [Mat. Sb. (N.S.), 1949, 25(67) :2, 275–306 Quasi-geodesic lines on a convex surface Pogorelov].
Is the same true ...
- 4,713
17
votes
4
answers
772
views
Partitions of $\mathbb{R}^d$ by implicit polynomial equations
Given a polynomial
$p(x_1,x_2,\ldots,x_d)$
in $d$ variables, with maximum degree $k$,
what is the maximum number of
components of $\mathbb{R}^d$ minus $p(\ldots)=0$?
In other words, into how many ...
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