# 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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?

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

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

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

**4**

votes

**1**answer

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

**1**

vote

**1**answer

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

**3**

votes

**0**answers

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

**9**

votes

**0**answers

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

**5**

votes

**0**answers

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

**2**

votes

**1**answer

53 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)\...

**5**

votes

**0**answers

112 views

### How does a map from permutahedra to associahedra factor through multiplihedra?

Let $P_i$ denote permutahedra, $K_i$ associahedra and $J_i$ multiplihedra. In their famous paper on operadic diagonals, Saneblidze and Umble use a projection $p_i: P_i \to K_{i+1}$ which factors as $...

**9**

votes

**2**answers

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

**3**

votes

**1**answer

80 views

### Solid angles at points in an orthosimplex

Given a point ${\bf x} = (x_1,x_2,\dots,x_n)$ in the orthosimplex $K = \{(x_1,x_2,\dots,x_n)\ : \ 0 \leq x_1 \leq x_2 \leq \dots \leq x_n \leq 1\}$, what proportion of a ball of radius $\epsilon$ ...

**16**

votes

**1**answer

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

**0**

votes

**0**answers

29 views

### Distance to the “boundary” of a polyhedral complex

Suppose I have a polyhedral complex $\{P_1, \ldots, P_k\}$ and let $S := \cup_{i = 1}^k P_i$. I am interested in a function which measures the distance from a point $x \in S$ to the "boundary&...