# 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

**10**answers

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

**7**answers

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

**4**answers

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

**3**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**14**answers

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

**8**answers

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

**2**answers

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

**3**answers

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

**1**answer

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 ...

**10**

votes

**3**answers

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

**3**answers

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

**1**answer

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

**5**answers

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

**3**answers

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

**2**answers

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

**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 ...

**18**

votes

**2**answers

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

**2**answers

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

**3**answers

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

**7**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**3**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**14**answers

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

**0**answers

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

**2**answers

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

**4**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**1**answer

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

**2**answers

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

**3**answers

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?
...