All Questions
Tagged with mg.metric-geometry convex-polytopes
48 questions
26
votes
7
answers
10k
views
Uniformly Sampling from Convex Polytopes
How to choose a point uniformly from a convex polytope $P \subset [0,1]^n$ defined by some inequalities, $Ax < b$? (Here $A$ is an $m \times n$ matrix, $x \in \mathbb{R}^n$, and $b \in \mathbb{R}^...
- 22.8k
44
votes
11
answers
26k
views
Algorithm for finding the volume of a convex polytope
It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
- 441
26
votes
2
answers
4k
views
3D models of the unfoldings of the hypercube?
There are (apparently) 261 distinct unfoldings of the 4D hypercube, a.k.a., the
tesseract, into 3D.1
These unfoldings (or "nets") are analogous to the 11 unfoldings of
the 3D cube into the plane.2
...
- 151k
58
votes
14
answers
19k
views
Open problems in Euclidean geometry?
What are some (research level) open problems in Euclidean geometry ?
(Edit: I ask just out of curiosity, to understand how -and if- nowadays this is not a "dead" field yet)
I should clarify a bit ...
63
votes
8
answers
14k
views
Fair but irregular polyhedral dice
I am interested in determining a collection of geometric conditions that will guarantee that a convex polyhedron
of $n$ faces is a fair die in the sense that, upon random rolling, it has an equal $1/n$...
- 151k
27
votes
3
answers
13k
views
Which unfoldings of the hypercube tile 3-space: How to check for isometric space-fillers?
Recently Mark McClure constructed and displayed
the 261 unfoldings of the hypercube (tesseract)
in response to the question,
"3D models of the unfoldings of the hypercube?":
The first 9 unfoldings ...
- 151k
21
votes
5
answers
1k
views
Is there a midsphere theorem for 4-polytopes?
The (remarkable) midsphere theorem says that each combinatorial
type of convex polyhedron may be realized by one all of whose edges are
tangent to a sphere
(and the realization is unique if the center ...
- 151k
18
votes
1
answer
644
views
Egalitarian measures
A question I got asked I while ago:
If $T$ is a triangle in $\mathbb R^2$, is there a function $f:T\to\mathbb R$ such that the integral of $f$ over each straight segment connecting two points in the ...
- 47.3k
16
votes
2
answers
590
views
Can you perturb an inscribed polytope so all its edges grow?
Consider the family of convex simplicial polytopes with vertices in the unit sphere of $\mathbb{R}^n$ which have the origin as an interior point.
My question is the following:
Let $P, P'$ be two non-...
4
votes
3
answers
347
views
Minimal data required to determine a convex polytope
Let $P\subset \Bbb R^d$ be a convex polytope.
Suppose that I know
its combinatorial type (aka. the face-lattice),
the length $\ell_i$ of each edge, and
the distance $r_i$ of each vertex from the ...
- 13.6k
36
votes
2
answers
2k
views
Bodies of constant width?
In two-dimensional case one can generalize figures of constant width as figures which can rotate in a convex polygon.
Here is one example which can be used to drill triangular holes:
I would like to ...
- 45k
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 ...
- 513
18
votes
1
answer
678
views
Higher dimensional generalization of: Any quadrilateral tiles the plane?
Any (non-self-intersecting) quadrilateral tiles the plane.
(MathWorld image.)
Q. What is the strongest known generalization of this statement to higher dimensions?
I.e., $\mathbb{R}^d$ ...
- 151k
18
votes
2
answers
986
views
"Derived" polyhedra and polytopes
The notion of derived polygon is natural and leads to remarkable convergence.
Start with a polygon, and replace it by locating a point on every edge
a fraction $\alpha$ between the two endpoints. For ...
- 151k
11
votes
1
answer
652
views
How to correctly state Cauchy's rigidity theorem?
Cauchy's rigidity theorem is often stated briefly as
Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent.
As a more formal generalization to general ...
- 13.6k
1
vote
1
answer
209
views
Is a polytope with vertices on a sphere and all edges of same length already rigid?
Let's say $P\subset\Bbb R^d$ is some convex polytope with the following two properties:
all vertices are on a common sphere.
all edges are of the same length.
I suspect that such a polytope is ...
- 13.6k
24
votes
1
answer
1k
views
Which unfoldings of the $d$-dimensional hypercube tile $(d{-}1)$-space?
A six year old question,
Which unfoldings of the hypercube tile $3$-space?, has just been answered by
Moritz Firsching:
All $261$ unfoldings tile space!
So now we know:
For $d=2$, the unfolding of ...
- 151k
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
20
votes
4
answers
950
views
The limit of edge-midpoint convex polyhedra
Starting with a convex polyhedron $P_1 \subset \mathbb{R}^3$,
replace that with $P_2$, the convex hull of the midpoints of the edges of $P_1$.
Continuing this process, we obtain a ...
- 151k
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
0
answers
577
views
"Japanese Theorem" on cyclic polygons: Higher-dimensional generalizations?
A beautiful theorem known as the Japanese Theorem (Wikipedia, MathWorld)
says that, no matter how one triangulates a cyclic (inscribed in a circle) polygon,
the sum of the radii of the incircles is ...
- 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
18
votes
1
answer
841
views
Known configurations maximizing the volume of the convex hull of n points on the unit sphere
For $n\geq 4$, let $V_n$ be the maximum volume of the convex hull of $n$ points on the unit sphere (in $\mathbb{R}^3$, although information on higher dimensions is welcome as well). I'm sure the ...
- 32.5k
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
1
answer
1k
views
Totally rational polytopes
Define a convex polytope in $\mathbb{R}^d$ as
totally rational (my terminology)
if its vertex coordinates are rational, its edge lengths
are rational, its two-dimensional face areas are rational, etc.,...
- 151k
17
votes
2
answers
2k
views
Efficiently determine if convex hull contains the unit ball
Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time (in both $n$ and $d$)? The convex ...
- 3,377
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
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
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 ...
- 532
13
votes
0
answers
252
views
Does there always exist a self dual polytope that contains a given polytope contained in its dual?
Suppose a polytope $P$ is contained in its dual polytope $\tilde{P}$. Does there always exist a polytope $Q$ that contains $P$ and is self dual $Q=\tilde{Q}$? Is there any bound on the minimal number ...
- 241
10
votes
3
answers
500
views
Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increases in length, can the circumradius still get larger?
Let $P\subset \Bbb R^n$ be an inscribed convex polytope, that is, all its vertices are on a common sphere of radius $r$.
Let $G$ be the edge-graph of $P$. For convenience, assume $V(G)=\{1,\dotsc,s\}$....
- 13.6k
10
votes
2
answers
845
views
Largest regular $k$-simplex inscribed in a $d$-cube, $k < d$
The largest (by edge length) regular simplex inscribed in a unit cube
is well known in $\mathbb{R}^2$ and $\mathbb{R}^3$:
Image sources:
left: NMSU,
right: Mathworld.
A recent Amer ...
- 151k
9
votes
1
answer
240
views
Cyclic polygons generalized to higher dimensions
Many theorems hold for cyclic polygons—convex polygons inscribed
in a circle. Perhaps the most basic is this,
from the reference cited below:
Theorem. There exists a cyclic polygon of $n \ge ...
- 151k
8
votes
3
answers
390
views
Is there any edge- but not vertex-transitive polytope in $d\ge 4$ dimensions?
I consider convex polytopes $P\subset\Bbb R^d$. The polytope is called vertex- resp. edge-transitive, if any vertex resp. edge can be mapped to any other by a symmetry of the polytope.
I am looking ...
- 13.6k
8
votes
3
answers
1k
views
Area of cross-section (at midpoint perpendicular to longest diagonal) in the unit cube of dimension N
Take a unit cube (of side 1) in N dimensions. Construct the cross-section at the midpoint of the longest diagonal. What is the area of this N-1 dimensional region? I can compute this, but it would be ...
- 81
7
votes
2
answers
392
views
Convex deltahedra in higher dimensions
There are eight convex polyhedra whose faces are equilateral triangles, so-called
deltahedra:
(Image from here)
Q. Have the equivalent higher-dimensional ...
- 151k
7
votes
0
answers
162
views
Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets
We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
- 1,677
7
votes
1
answer
648
views
Maximal volume of a simplex inscribed in a spherical cap
Let $B_n$ be the $n$-dimensional unit ball, and $B_n(\varepsilon)$ be the spherical cap with height $\varepsilon$ I am interested in the quantity
$$\Gamma:=\sup_{\Delta:\textrm{ inscribed simplex in }...
- 599
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
6
votes
1
answer
212
views
A polytope with congruent facets and an insphere that is not facet-transitive?
Is there a $d$-dimensional convex polytope (convex hull of finitely many points, not contained in a proper subspace), with $d\ge 4$ and the following properties?
All facets are congruent,
it has an ...
- 13.6k
6
votes
2
answers
3k
views
Finding the convex combination of vertices which yields an inner point of a polytope
Given a convex polytope $P\in \mathbb{R}^n$, and a point $x\in P$, Caratheodory's theorem gives us that there exists a set of at most $n+1$ vertices of $P$, such that $x$ is a convex combination of ...
- 243
5
votes
3
answers
683
views
Alexandrov's generalization of Cauchy's rigidity theorem
Wikipedia states that A. D. Alexandrov generalized Cauchy's rigidity theorem for polyhedra to higher dimensions.
The relevant statement in the article is not linked to any source. The sources at the ...
- 13.6k
5
votes
2
answers
294
views
Convex caps with prescribed edges
Let $P$ be a convex polygon in the plane $R^2=R^2\times \{0\}$, and $E$ be the edge graph of some subdivision of $P$ into convex polygons, which is $3$-connected. Does there exist a convex polyhedral ...
- 7,149
4
votes
0
answers
132
views
Can a polytopal graph be "centrally symmetric" in more than one way?
Let $P,Q$ be two centrally symmetric convex polytopes, potentially of different dimensions and combinatorial type, but with the same edge-graph $G$.
The central symmetry of $P$ induces an involutory ...
- 13.6k
4
votes
1
answer
250
views
Zoll Flat Finsler tori and convex bodies on a starry night
The starry night. The "celestial sphere" is given by set of non-zero vectors in $\mathbb{R}^n$ modulo positive dilations (i.e., $v \equiv w$ if $v = \lambda w$ for some $ \lambda > 0$) and the "...
- 13.5k
4
votes
2
answers
812
views
Is it possible to sample uniformly on the surface of a high-dimensional polytope?
There are some pretty simple methods to do uniform sampling on the surface of high-dimensional spheres or cubes.
Are there any methods that sample uniformly on the surface of a high-dimensional ...
- 143
0
votes
0
answers
98
views
Asymptotic optimal sphericity
How quickly does maximum sphericity of polyhedra with $n$ faces approach 1 as $n→∞$? I can show that sphericity $1 - \frac{5 \sqrt{3} π}{27n} - O(n^{-3/2})$ is possible. Is this, especially $O(n^{-3/...
- 7,545
0
votes
4
answers
457
views
Confining a polytope to one side of an affine hyperplane
Judging whether one convex polytope is inside of another when both are expressed as a system of linear inequalities seems not to be an easy problem.
This answer on math.stackexchange.com claims the ...
- 2,239