# 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

773
questions

**8**

votes

**0**answers

253 views

### Integral representations of finite groups and lattice point geometry

See the edit at the bottom (April 2021)
This contains both a reference request, and a specific problem.
Let $K$ be a finite group, and let $\theta: K \to {\rm GL}(d,{\bf Z})$ be a (faithful) group ...

**1**

vote

**0**answers

87 views

### Integrality of polyhedra

Given two polyhedra in $H$ representation $P_1:Ax\leq b$ and $P_2:Bx\leq c$ which are integral are bounded when is their intersection also integral?
Given two polyhedra in $H$ representation $P_1:Ax\...

**2**

votes

**0**answers

81 views

### How to judge whether the following convex set contains a given point?

Let the set $\mathcal{S}=\left\{ \sum_{i=1}^n x_i\mathbf{h}_i：x_i\in[0,1] \text{ for all }i\right\}\subset\mathbb{R}^r$, i.e., a zonotope generated by $n$ column vector $\mathbf{h_1},\cdots,\mathbf{h}...

**0**

votes

**0**answers

21 views

### Sectioning facets from Coxeter-Dynkin diagram

Terminology: a sectioning facet $Q$ of a $D$-dimensional polytope $P$ is another polytope which uses a $(D-1)$-dimensional subset of $P$’s vertices and edges and is maximal (it is not a diminishing of ...

**0**

votes

**0**answers

59 views

### Number of vertices in a polyhedron

Consider polytopes
$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$
$$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$
$$B[z_{1},z_{2},z]'\leq c$$
having vertex count $v_1,v_2$ and $v$ respectively.
We ...

**2**

votes

**0**answers

36 views

### An easy way to recognize the edges of an orbit polytope?

Given a finite (orthogonal) matrix group $\Gamma\subseteq\mathrm O(\Bbb R^d)$ and a point $x\in\Bbb R^d$. The corresponding orbit polytope is
$$\mathrm{Orb}(\Gamma,x):=\mathrm{conv}\{Tx\mid T\in \...

**3**

votes

**0**answers

23 views

### Intrinsic definition of a cone in a normal fan

Let $P\subseteq \mathbb{R}^n$ be a full dimensional polytope. Let us assume that $P$ has a facet description with the following inequalities:
$$ \left<x,u_F\right> \geq -a_F$$
where $u_F\in \...

**1**

vote

**0**answers

25 views

### How to express a polytope by a matrix inequalty? [duplicate]

Consider a convex V-polytope generated by the origin and $n$ points $\mathbf{h}_1,\cdots,\mathbf{h}_n$ in $\mathbb{R}^r$. A Theorem in the area of convex geometry shows that each V-polytope is a H-...

**4**

votes

**1**answer

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

**5**

votes

**1**answer

100 views

### A combinatorial characterization of the central inversion of a polytope?

Given a convex full-dimensional polytope $P\subset\Bbb R^d$ (convex hull of finitely many points and not contained in any proper affine subspace) and a symmetry thereof (a linear map $\smash{T\in\...

**2**

votes

**0**answers

76 views

### Is the projective symmetry group of a polytope more general than its linear symmetry group?

Give a (convex) polytope $P\subset\Bbb R^d$ (the convex hull of finitely many points). Consider its linear and projective symmetry groups:
\begin{align}
\DeclareMathOperator{\Aut}{Aut}
\...

**2**

votes

**3**answers

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

**3**

votes

**0**answers

45 views

### Classifying/enumerating vertex-transitive simplicial polytopes

I'm interested in understanding the class of simplicial polytopes in $\mathbb R^n$ whose Euclidean isometry group $G$ acts transitively on the vertices. These are examples that I know of:
simplicial ...

**4**

votes

**1**answer

241 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 $\...

**10**

votes

**2**answers

572 views

### Symmetries and faces of the associahedron

The dihedral group of order $2n+2$ acts on $K_n$, the ($n-2$)-dimensional associahedron. Are there any other symmetries? References?
Does the answer to 1 change if we restrict to just the 1-...

**4**

votes

**0**answers

107 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

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

**8**

votes

**0**answers

84 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

45 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

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

**6**

votes

**2**answers

88 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

79 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

66 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

304 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

60 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

157 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

180 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

93 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

299 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

114 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

75 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

168 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

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

**37**

votes

**10**answers

20k 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

119 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

140 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

173 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

702 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

506 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

132 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

264 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

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

**0**

votes

**0**answers

33 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

394 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

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