All Questions
Tagged with mg.metric-geometry discrete-geometry
671 questions
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
21
votes
0
answers
741
views
+300
Snakes on a plane
A sleeping bag for a baby snake in $d$ dimensions (no, really) is a subset of $\mathbb{R}^d$ which can cover (via translation and rotation) every (piecewise-smooth for concreteness) curve of unit ...
- 20.5k
20
votes
3
answers
3k
views
How many unit squares can you pack into a rectangle with nearly integer side lengths?
Earlier today, somebody asked what looks like a homework problem, but admits the following reading which I think is interesting:
Suppose $a_1,\dots, a_n$ are positive integers, and $\varepsilon$ is ...
20
votes
1
answer
452
views
Hidden points in polygons
Let $h(n)$ be the largest number of mutually invisible points that can be located in a
polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment
$xy$ contains a point ...
- 151k
20
votes
1
answer
591
views
Update to Shephard's "Twenty Problems on Convex Polyhedra"
Forty-three years ago, Geoffrey Shephard published an influential list of open problems
on convex polyhedra.
Progress has been made on several of his problems, and perhaps some have been completely ...
- 151k
20
votes
0
answers
433
views
Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?
Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation
it stays a convex polytope,
it stays a combinatorial dodecahedron (i.e. its ...
- 13.6k
19
votes
5
answers
21k
views
Dividing a square into 5 equal squares
Can you divide one square paper into five equal squares?
You have a scissor and glue. You can measure and cut and then attach as well. Only condition is You can't waste any paper.
- 383
19
votes
1
answer
928
views
Can every simple polytope be inscribed in a sphere?
It is known that not every convex polytope (even polyhedron, e.g. this one) can be made inscribed, that is, we cannot always move its vertices so that
all vertices end up on a common sphere, and
the ...
- 13.6k
19
votes
2
answers
1k
views
Four Dimensional Origami Axioms
What are the axioms of four dimensional Origami.
If standard Origami is considered three dimensional, it has points, lines, surfaces and folds to create a three dimensional form from the folded ...
- 193
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
18
votes
3
answers
405
views
Tilting the $d$-cube to vertically separate its vertices
Let $C_d$ be a unit edge-length cube in $d$ dimensions.
I would like to orient it ("tilt" it) so that the vertical (last) coordinates
of its $2^d$ vertices are maximally separated, in the sense
that ...
- 151k
18
votes
2
answers
667
views
Total length of a set with the same projections as a square
Take some convex polygon $P$. I'm mostly asking about the unit square, but would also appreciate thoughts on general polygons. We want to take a family of line segments inside $P$ that have the same ...
- 1,160
18
votes
3
answers
2k
views
Are the Platonic solids shadows of 4-polytopes?
Say that a 3D shadow of a 4-polytope is a parallel projection to 3-space, not necessarily orthogonal to that 3-space (that would make it an orthogonal projection).
I am wondering if each of the five ...
- 151k
18
votes
2
answers
573
views
Can the graph of a symmetric polytope have more symmetries than the polytope itself?
I consider convex polytopes $P\subseteq\Bbb R^d$ (convex hull of finitely many points) which are arc-transitive, i.e. where the automorphism group acts transitively on the 1-flags (incident vertex-...
- 13.6k
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
17
votes
4
answers
1k
views
Can I build infinitely many polytopes from only finitely many prescribed facets?
Given a finite set of convex $d$-dimensional polytopes $\mathcal P$, for some $d\ge 2$.
Question: Is it true that there are only finitely many different convex $(d+1)$-dimensional polytopes whose ...
- 13.6k
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
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 ...
- 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
17
votes
1
answer
390
views
17
votes
0
answers
488
views
Large almost equilateral sets in finite-dimensional Banach spaces
Question: Does there exist a function $C:~(0,1)\to
(0,\infty)$ such that for each $\varepsilon\in(0,1)$ every Banach space
$X$ of dimension $\ge C(\varepsilon)\log n$ contains an $n$-point
set $\{x_i\...
- 4,878
17
votes
0
answers
731
views
Does every connected set that is not a line segment cross some dyadic square?
A dyadic square is a subset of $R^2$ of the form $x + 2^{-n} [0,1]^2$ with $x \in 2^{-m} Z^2$, for integers $m,n \geq 0$. We say that a set $A$ crosses a square $S$ if there exists a connected subset ...
- 171
16
votes
3
answers
2k
views
Are infinite planar graphs still 4-colorable?
Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a ...
- 151k
16
votes
4
answers
3k
views
covering by spherical caps
Consider the unit sphere $\mathbb{S}^d.$ Pick now some $\alpha$ (I am thinking of $\alpha \ll 1,$ but I don't know how germane this is). The question is: how many spherical caps of angular radius $\...
- 96.4k
16
votes
5
answers
717
views
Minimal blocking objects with shadows like a cube
This is a more geometric version of the previous question,
"Lattice-cube minimal blocking sets". I will first specialize to $\mathbb{R}^3$, $d=3$.
View an $n \times n \times n$ cube $C_3(n)$ as ...
- 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
16
votes
2
answers
1k
views
Integer lattice points on a hypersphere
Is the following statement true?
For every integer $n\ge2$ and every integer $k\ge0$ there exists a hypersphere in $\mathbb{R}^n$ (circle, sphere etc) containing exactly $k$ integer lattice points ...
- 513
16
votes
1
answer
888
views
Kakeya crossed-needles problem
The Kakeya needle problem asks for the
minimum area planar region in which one can completely turn around a line segment through
a series of translations and rotations. There is no minimum: There are &...
- 151k
16
votes
2
answers
5k
views
Weighted area of a Voronoi cell
Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
- 195
16
votes
3
answers
2k
views
A random walk on random lines
I am wondering if this random walk remains finite with positive probability.
Start with three lines $A,B,C$ that are extensions of an equilateral triangle.
Let $p_0$ be one corner. Generate a line $...
- 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
16
votes
2
answers
1k
views
Are Penrose tilings universal? Do aperiodic universal tilings exist?
Consider a tiling of the plane using tiles of at least two types (e.g, a Penrose tiling such as that shown at the bottom of this question, which tiles the plane with two types of tiles). List the tile ...
- 4,922
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
16
votes
1
answer
774
views
Minimizing the excursion of a sum of unit vectors
I have $n$ unit-length vectors $v_i$ in $\mathbb{R}^3$, whose
sum is zero:
$$ v_1 + v_2 + \cdots + v_n = 0 \; .$$
Now I form the closed polygon $P$ in space by placing them head to tail.
So the ...
- 151k
16
votes
1
answer
537
views
Balls in Hilbert space
I recently noticed an interesting fact which leads to a perhaps difficult question. If $n$ is a natural number, let $k_n$ be the smallest number $k$ such that an open ball of radius $k$ in a real ...
- 2,049
16
votes
0
answers
298
views
Realization spaces of 3-dimensional polytopes with fixed face areas
It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible.
A proof of this theorem can be found for instance in ...
- 31.2k
15
votes
2
answers
2k
views
Partitioning a Rectangle into Congruent Isosceles Triangles
Is it possible to partition any rectangle into congruent isosceles triangles?
- 404
15
votes
3
answers
9k
views
$n$-dimensional Voronoi diagram
I need to compute the Voronoi diagram of a set of points in $R^n$.
I'm quite unschooled on the topic, could someone point me to the right references so that I can
a) understand the theory behind it;
b)...
- 253
15
votes
3
answers
1k
views
covering a square with unit squares
Can some square of side length greater than $n$ be covered by $n^2+1$ unit squares? (The unit squares may be rotated. The large square and its interior must be covered.)
- 897
15
votes
2
answers
779
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 ...
- 161
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
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 \...
- 1,284
15
votes
2
answers
571
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-\...
- 151k
15
votes
1
answer
530
views
Dividing a polyhedron into two similar copies
The paper Dividing a polygon into two similar polygons proves that there are only three families of polygons that are irrep-2-tiles (can be subdivided into similar copies of the original).
Right ...
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
15
votes
1
answer
640
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-\...
- 6,101
15
votes
2
answers
863
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. (...
- 153
15
votes
1
answer
838
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 ...
- 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
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 ...
- 169