Questions tagged [convex-polytopes]
Convex polytopes are the convex hulls of a finite set of points in Euclidean spaces. They have rich combinatorial, arithmetic, and metrical theory, and are related to toric varieties and to linear programming
98
questions
36
votes
10answers
19k 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 ...
17
votes
7answers
6k 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}^...
18
votes
4answers
2k views
Can you determine whether a graph is the 1-skeleton of a polytope?
How do I test whether a given undirected graph is the 1-skeleton of a polytope?
How can I tell the dimension of a given 1-skeleton?
15
votes
3answers
1k views
Guises of the Stasheff polytopes, associahedra for the Coxeter $A_n$ root system?
Richard Stanley keeps a famous running compilation of different guises of the celebrated Catalan numbers. The number of vertices of the associahedron is one instantiation among the multitude, and the ...
10
votes
2answers
2k views
Given the vertices of a convex polytope, how can we construct its half-space representation?
Let us say I have the vertices of a polytope $V = \{v_1,\dots,v_k\} \subset \mathbb R^n$. Is it possible to write $V$ as intersection of half-spaces using the information from the vertices, i.e., can ...
20
votes
2answers
2k 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
...
8
votes
1answer
302 views
Loday's characterization and enumeration of faces of associahedra (Stasheff polytopes)
From "The multiple facets of the associahedra" by Loday:
Let us consider the formal power series
$$f(x) = x+a_1 x^2 +a_2 x^3 + \cdots+ a_n x^{n+1} + \cdots$$
and let
$$ g(x) = x+b_1 x^2 + ...
70
votes
2answers
8k views
The amplituhedron minus the physics
Is it possible to appreciate the geometric/polytopal properties of the amplituhedron without delving into the physics that gave rise to it?
All the descriptions I've so far encountered assume ...
52
votes
14answers
15k 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 ...
57
votes
8answers
11k 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$...
16
votes
2answers
5k views
How many vertices can a convex polytope have?
One has an $n$-dimensional convex polytope $P$ represented by an intersection of half-spaces:
\begin{equation}H_i = \{ (x_1,x_2, \ldots,x_n) \in \mathbb{R}^n \mid \sum_{j=1}^n a_{ij} x_j \ge a_{i0}, \...
8
votes
3answers
5k views
Random Sampling a linearly constrained region in n-dimensions…
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
18
votes
1answer
602 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 ...
asked Nov 27 '09 at 16:53
Mariano Suárez-Álvarez
43.8k11 gold badges128 silver badges251 bronze badges
10
votes
3answers
1k views
On maximal regular polyhedra inscribed in a regular polyhedron
Let T, C, O, D, or I be regular tetrahedron, cube, octahedron, dodecahedron, and icosahedron, respectively. Suppose that the outer polyhedron have edge-length 1.
For example, it's easy to prove that ...
4
votes
3answers
247 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 ...
2
votes
1answer
252 views
Relating face polytopes of permutohedra to integer partitions
The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...
54
votes
5answers
2k views
Unusual symmetries of the Cayley-Menger determinant for the volume of tetrahedra
Suppose you have a tetrahedron $T$ in Euclidean space with edge lengths $\ell_{01}$, $\ell_{02}$, $\ell_{03}$, $\ell_{12}$, $\ell_{13}$, and $\ell_{23}$. Now consider the tetrahedron $T'$ with edge ...
24
votes
3answers
825 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 ...
12
votes
2answers
1k views
Combinatorics of the Stasheff polytopes
First a little background for those unaware. The Stasheff polytopes (or associahedra) are certain convex polytopes that arise in the theory of $A_\infty$-algebras. There is one polytope for each $n\...
19
votes
5answers
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 ...
18
votes
2answers
791 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 ...
35
votes
2answers
1k views
Bodies of constant width?
In two-dimensional case one can generalize figures of constant width as figures which can rotate in a covex polygon.
Here is one example which can be used to drill triangular holes:
I would like to ...
23
votes
3answers
2k views
How many different numbers can be obtained as product of first $n$ natural numbers?
Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...
11
votes
7answers
4k views
coordinates of vertices of regular simplex
For $d=3$, vertex coordinates of a regular simplex have a simple expression since vertices correspond to four vertices of a cube. Is there a simple expression for higher dimensions? In particular I'm ...
10
votes
1answer
437 views
Tighter Caratheodory on the moment curve?
The moment curve is the set of points of the form
$$(t,t^2,t^3,...,t^n) \in R^n$$
Let $M$ be the portion of the moment curve where $t\in [0,1]$, and let $\overline{M}$ be the convex hull of $M$.
...
17
votes
1answer
514 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$ ...
9
votes
0answers
145 views
How to correctly state Cauchy's rigidity theorem?
Cauchy's rigidity theorem is usually cites briefly as
Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent.
As a more formal generalization to general ...
3
votes
0answers
232 views
Guises of the refined Eulerian numbers, generated by tangent vectors (OEIS A145271)
The Eulerian numbers (OEIS A008292, not to be confused with the Euler numbers) pop up in numerous scenarios in combinatorics and advanced analysis, one as the components of the h-vectors of the ...
15
votes
3answers
522 views
Can we realize a graph as the skeleton of a polytope that has the same symmetries?
Given a graph $G$, a realization of $G$ as a polytope is a convex polytope $P\subseteq \Bbb R^n$ with $G$ as its 1-skeleton.
A realization $P\subseteq \Bbb R^n$ is said to realize the symmetries of $...
12
votes
2answers
1k views
An integrality question about expressing an integer as a product of numbers below $n$
Let $n\ge 2$ be a natural number. Suppose that $N$ is a natural number, composed only of primes below $n$, and that can be expressed as
$$
N= \prod_{j=1}^{n} j^{x_j}
$$
where $x_1$, $\ldots$, $x_n$...
5
votes
1answer
224 views
Classification of vertex-transitive zonotopes
Zonotopes are convex polytopes that can be defined in several equivalent ways:
parallel projections of cubes,
Minkowsi sums of line segments,
only centrally symmetric faces,
...
I wonder whether ...
1
vote
1answer
142 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 ...
54
votes
1answer
2k views
Intersecting Family of Triangulations
Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
27
votes
14answers
6k views
Generalizations of the Birkhoff-von Neumann Theorem
The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices.
The question is to point out different ...
24
votes
0answers
2k views
Why do polytopes pop up in Lagrange inversion?
I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
25
votes
2answers
1k views
Complete the following sequence: point, triangle, octahedron, . . . in a dg-category
Let $\mathcal C$ be a pre-triangulated dg-category (or a stable $\infty$-category, if you wish).
An object $X$ in $\mathcal C$ gives a "point":
$$X$$
A morphism $X\xrightarrow f Y$ in $\mathcal C$ ...
18
votes
4answers
771 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 ...
11
votes
1answer
2k views
Characterizing faces of 3-dimensional polyhedra. (Related to Victor Eberhard's Theorem [1890]:)
Originally asked by Ali Dino Jumani; EXTENSIVELY EDITED by David Speyer. The previous version was a bit confused, but Steven Sivek and Graham, in the comments, figured out what was going on.
G. C. ...
14
votes
0answers
468 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 ...
19
votes
0answers
486 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 ...
19
votes
2answers
1k views
About a Delzant polytope. (In particular dodecahedron)
Hi. I have a question.
Definition. Delzant polytope $P$ is a rational convex simple polytope with the smooth condition. Here, "smooth" means that for each vertex $v$, the $n$ edges containing $v$ ...
16
votes
1answer
823 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.,...
13
votes
0answers
240 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 ...
5
votes
3answers
519 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 ...
8
votes
1answer
191 views
Classifying two-faces of four-polytopes
Motivation: This question is related to my study of hyperbolic Coxeter polytopes. In general, if one put some restrictions on the type of their dihedral angles (say, all dihedral angles are equal to $\...
7
votes
1answer
274 views
The $32$-deg polynomial for the tetrahedron inscribed in the icosahedron?
This MO answer discusses this table involving the maximal side lengths of the five Platonic solids $T,C,O,D,I$ inscribed in the other solids,
This table is also found in Moritz Firsching's paper. I ...
19
votes
3answers
2k views
Sampling from the Birkhoff polytope
The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope
Recently someone asked me if I knew
How to sample (in polynomial time) ...
16
votes
1answer
376 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-...
16
votes
2answers
4k 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$. ...
12
votes
3answers
616 views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
