# 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

766
questions

**1**

vote

**0**answers

21 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 to be a complex problem.
This answer on math.stackexchange.com claims the ...

**3**

votes

**1**answer

149 views

### Iterating projections to random halfspaces

Consider the following process:
Start with a set $S = \mathbb R^n$. Repeat $L$ times: choose a random orthonormal basis $u_1, \ldots, u_n$, and consider the cone $C = \{ \sum \alpha_i u_i : \alpha_i \...

**0**

votes

**0**answers

54 views

### Integer Fourier-Motzkin elimination of special polyhedron

I have a set of integral points in a convex region
$$P_0=\{(x,y)\in\mathbb Z^{m'+n}:\mbox{ }A[x,y]'\leq b\}$$
where $P_0$ is identical to $P_1$ below
$$P_1=\{x\in\mathbb Z^n:\exists\mbox{ exactly one }...

**4**

votes

**0**answers

83 views

### “Baues poset” of shellings of simplicial polytope?

Let me start with some background I want to use as analogy.
Consider a (convex) polytope $P$ and its set of triangulations. Among all the triangulations, a well behaved subset are the regular ones: ...

**14**

votes

**1**answer

474 views

### Tetrahedra passing through a hole

Assume a plane $P\subset\mathbb R^3$ has a hole $H$, and that the hole is topologically a compact disc. Being so, $P\setminus H$ does not separate the space. A regular tetrahedron $\sigma^3$ (of edge-...

**0**

votes

**0**answers

59 views

### On number of facets in projected polytopes of certain sparseness

$\DeclareMathOperator\Set{Set}$
Let
$Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$
where $A$ has $r=km$ rows and $k=O(1)$.
I am trying to write
$$
Set=\{x\in\...

**7**

votes

**0**answers

75 views

### Can solutions to Thomson's problem have pentagons?

Thomson's problem asks for the minimum energy configuration for $N$ electrons on a sphere (refs: https://en.wikipedia.org/wiki/Thomson_problem, https://sites.google.com/site/adilmmughal/...

**1**

vote

**0**answers

41 views

### Decomposition of Polyhedral - An example

There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...

**14**

votes

**1**answer

523 views

### Inequalities for marginals of distribution on hyperplane

Let $H = \{ (a,b,c) \in \mathbb{Z}_{\geq 0}^3 : a+b+c=n \}$. If we have a probability distribution on $H$, we can take its marginals onto the $a$, $b$ and $c$ variables and obtain three probability ...

**47**

votes

**4**answers

2k views

### How many ways can you inscribe five 24-cells in a 600-cell, hitting all its vertices?

You can inscribe five tetrahedra in a dodecahedron so that each vertex of the dodecahedron is the vertex of just one tetrahedron, as drawn here by Greg Egan:
Warmup question: How many ways can you do ...

**2**

votes

**1**answer

104 views

### Anchor sets for lattice polygons: Part I

Suppose $V=\{(x_1,y_1), (x_2,y_2),\dots,(x_v,y_v)\}$ is a vertex set of lattice points satisfying
$$0=x_1<x_2<\dots<x_v \qquad \text{and} \qquad y_1>y_2>\cdots>y_{v-1}>y_v=0.$$
...

**5**

votes

**2**answers

85 views

### Partitions of convex planar regions into zonogons

A zonogon is a centrally symmetric convex polygon.
Are there convex non-zonogons that can be partitioned into a finite number of (convex) zonogons?
Same as 1 with the pieces allowed to be nonconvex ...

**1**

vote

**1**answer

74 views

### Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]

Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...

**3**

votes

**0**answers

63 views

### Additional symmetries of the Traveling Salesman Polytope

Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...

**14**

votes

**2**answers

298 views

### Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?

For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices
$$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\
\pi_{2,1} & \ddots & \...

**2**

votes

**1**answer

58 views

### Are zonotopes determined by their edge-graph?

General polytopes are not determined by their edge-graph (up to combinatorial equivalence). But I came accross the statement that zonotopes are determined in this way.
Question: Is this true? And ...

**3**

votes

**1**answer

153 views

### Cohomology ring of a hypersurface in toric variety

Let $X^n$ be a smooth projective toric variety corresponding to a simple polytope $P$. It is well known that the cohomology ring $H^*(X)$ can be described in terms of combinatorics of faces of $P$.
...

**8**

votes

**1**answer

175 views

### Are there centrally-symmetric self-dual polytopes in dimension $d> 4$?

A convex polytope $P\subset\Bbb R^d$ is centrally symmetric if $-P=P$. It is self-dual (or better, self-polar?) if its polar dual $P^\circ$ is congruent to $P$, that is, there is a map $X\in\mathrm O(\...

**0**

votes

**1**answer

64 views

### If there are eigenvectors with largest components $i$ resp. $j$, then is there an eigenvector with two largest components $i$ and $j$?

Let $G=(V,E)$ be a connected (finite simple) graph with vertex set $V=\{1,...,n\}$ and let $\theta_2\in\Bbb R$ be the second-largest eigenvalue of its adjacency matrix. I wonder about the following ...

**2**

votes

**1**answer

92 views

### Minimum Euclidean squared norm in the convex hull of points with rational coordinates

This is probably known, but I have not located a reference.
Let $P$ be the convex hull of $k$ points in $\mathbb R^n$ with rational coordinates. Consider the Euclidean square norm function $F:P\to\...

**7**

votes

**2**answers

296 views

### Can two non-equivalent polytopes of same dimension have the same graph?

By a polytope I mean the convex hull of finitely many points. The graph of a polytope is the graph isomorphic to its 1-skeleton. By equivalence of polytopes I mean combinatorial equivalence, i.e. ...

**4**

votes

**2**answers

110 views

### Existence of a fundamental domain for the convex hull of group action on a rational polytope

Let $P \subset \mathbb R^n$ be a compact rational polytope (the affine space spanned by $P$ may not be $\mathbb R^n$). Let $G \subset {\bf GL}(n,\mathbb Z)$ be an arithmetic group. Let $$C = {\rm Conv}...

**2**

votes

**1**answer

73 views

### State-of-the-art article on “uniform 5-polytopes?”

I would like to read article(s) that provide the “state of the art” on the following open problem:
“Enumerate all convex uniform 5-polytopes.”
This problem is posted on the “Open Problem Garden” (http:...

**3**

votes

**1**answer

166 views

### What are midway sections of simplices?

This is a (slightly modified) crosspost.
Subsequent edit - coordinates are changed to obtain simpler expressions; the existing answer is not affected.
There is a family of convex polytopes: $P_n$ is $...

**0**

votes

**0**answers

34 views

### Attached convex “hulls”

Let $\mathcal{P}$ a finite set of points of a Euclidean $\mathbb{E}^n$ and take the union $\mathrm{U}(\mathcal{P})$ of all closed half-spaces defined by $n$ elements of $\mathcal{P}$ that contain only ...

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

**7**

votes

**2**answers

114 views

### Constructing a $0/1$ polytope from an abstract simplicial complex

Let us fix $\Delta$ a finite simplicial complex, and label the vertices of $\Delta$ as $\{1,2,\ldots,n\}$. For each $F\in \Delta$ let us consider the point in $\mathbb{R}^n$ given by:
$$e_F := \sum_{i\...

**5**

votes

**1**answer

139 views

### Is there a polytope with an essentially unique shape?

More percisely:
Question: Is there a (convex) polytope that has a unique realization up to, say, projective transformations?
I suppose I have to assume that it has more than $d+2$ vertices/facets if ...

**4**

votes

**2**answers

167 views

### Is there more than one pseudo-Catalan solid?

This question was asked on MSE a year ago. Motivation for this question can be found in other MSE questions here, here or here.
Convex solids can have all sorts of symmetries:
the platonic solids are ...

**12**

votes

**1**answer

682 views

### Two questions on the permutohedron

The $n$-dimensional permutohedron $P_n$ is the polytope given by the convex hull of all the possible permutations of the vector $(1,2,\dots,n+1)\in\mathbb{R}^{n+1}$. So it has $(n+1)!$ vertexes.
I ...

**3**

votes

**2**answers

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

**3**

votes

**2**answers

128 views

### If a polytope is centrally symmetric and combinatorially equivalent to a zonotope, is it a zonotope?

A zonotope is a polytope whose 2-faces are centrally symmetric.
Question: If a polytope $P$ is centrally symmetric and combinatorially equivalent to a zonotope, is it itself a zonotope?

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

**3**

votes

**1**answer

257 views

### An example in symplectic geometry

$\DeclareMathOperator\SU{SU}$Let $M$ be a coadjoint orbit of dimension 6 of $\SU(3)$, and let $T$ be the maximal torus in $\SU(3)$. If we denote $\mu : M \longrightarrow \mathbb{R}^2$ the moment map ...

**3**

votes

**1**answer

92 views

### Maximal number of visible vertices

Let $P$ be a three-dimensional convex polytope with $N$ faces; $O$ a point outside $P$. What is the maximal number $f(N)$ of vertices of $P$ which may be seen from $O$?

**3**

votes

**0**answers

102 views

### Edges in the convex hull of the union of random polygons

Let $P$ and $Q$ be two convex polygons in $\mathbb{R}^2$. Given $a > 0$, denote by $aP$ its image under the dilation by $a$ centered around the origin (i.e. the polygon obtained by replacing each ...

**4**

votes

**1**answer

226 views

### Polynomial size embeddings of toric varieties from polytopes?

Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan.
$X_P$ is always projective, because the collection of characters corresponding to the points $\...

**0**

votes

**0**answers

32 views

### Conditions on $a_i,b_i$ for $i =1,\ldots,n$, so that $\arg\max_{\|x\| \le 1}\min\{a_i^\top x + b_i\mid i = 1,\ldots,n\} \subseteq \{\|x\| < 1\}$

Let $A$ be an $n \times m$ matrix with rows $ a_1,\dots,a_n \in \mathbb R^m$ and let $b=(b_1,\dots,b_n)$ be a vector in $\mathbb R^n$. Let $\mathbb B_m$ be the centered closed unit-ball in $\mathbb R^...

**4**

votes

**0**answers

390 views

### Convex polytopes as “products” of lower dimensional polytopes of the same family

This MO-Q details the sense in which an associahedron is a product of lower dimensional associahedra, and this MSE-Q indicates the same is true for permutohedra.
Is there a reference which classifies ...

**0**

votes

**1**answer

93 views

### If $C_1\subseteq C_2$ are two closed convex cones that are pointed with $\partial C_1\subseteq \partial C_2$ then is $C_1=C_2$?

Let $C_1$ and $C_2$ be two proper full dimensional closed convex cones in $\mathbb{R}^n$ that are pointed. Suppose that $C_1\subseteq C_2$ and that the boundary of $C_1$ is contained in the boundary ...

**1**

vote

**1**answer

91 views

### Exact volume calculation of a polytope is NP hard under which restrictions?

Computing the exact volume of a polytope given in half space representation seems to be NP-hard. One paper I found proved it is hard for rational coefficients. (However, the paper itself was behind a ...

**4**

votes

**1**answer

61 views

### Mass distributions for high dimensional simplex and cross polytope

In this question, it is shown that the radial mass distribution of an $n$-cube (i.e. the probability density for the distance from a point selected uniformly from within an $n$-cube to the cube's ...

**6**

votes

**1**answer

159 views

### Edges of the contact polytope of the Leech lattice

Let $P\subset\Bbb R^{24}$ be the contact polytope of the Leech lattice, that is, $P$ is the convex hull of the 196,560 shortest vectors of $\Lambda_{24}$.
Question: What are the edges of $P$?
Let'...

**3**

votes

**0**answers

52 views

### How to find the dimension of the polar cone of a convex cone generated by some given vectors

Suppose we have access to a generating set $\{v_1, ..., v_k\}\subseteq\mathbb{R}^n$ of the convex cone $C=cone(v_1, ..., v_k)$, where $cone(\cdot)$ is the conical hull (i.e. nonnegative span) of ...

**2**

votes

**1**answer

46 views

### Is there a non-orthogonal linear deformation of a polytope that preserves edge-lengths and vertex-origin-distances?

Is there a polytope $P\subset\Bbb R^d$ (convex hull of finitely many points, not contained in a proper affine subspace), and a linear, but non-orthogonal transformation $T\in\mathrm{GL}(\Bbb R^d)\...

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

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

**4**

votes

**0**answers

87 views

### The area of cross-section of polyhedron or polytope

Consider a polyhedron or polytope $P$ in $\mathbb{R}^n$. Let $F$ be a bounded face of $P$. Now we shift and rotate this polyhedron such that $F$ lies on the hyperplane $\{t=0\}$, and $P\subseteq\...

**5**

votes

**0**answers

59 views

### Which polytopes can be deformed while keeping their edge-lengths?

Let $P\subset\Bbb R^d$ be a convex polytope (a convex hull of finitely many points). Lets call it flexible, if it can be continuously deformed while
keeping its combinatorial type, and
keeping its ...

**9**

votes

**2**answers

188 views

### Integer decomposition property with a partial order

Let $\mathcal{P}$ be a convex lattice polytope in $\mathbb{R}^n$. We say that $\mathcal{P}$ has the integer decomposition property (or "is IDP") if for all $k\in \mathbb{N}$ and $\alpha \in ...