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
942 questions
2
votes
2
answers
294
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\...
- 4,729
5
votes
1
answer
264
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 ...
- 13.6k
8
votes
1
answer
1k
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 ...
user82886
3
votes
2
answers
438
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?
- 13.6k
4
votes
2
answers
294
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 ...
- 4,432
3
votes
1
answer
332
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 ...
- 133
3
votes
1
answer
123
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$?
- 151
3
votes
0
answers
135
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 ...
- 2,216
0
votes
1
answer
108
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
218
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 ...
- 956
1
vote
1
answer
409
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 ...
- 121
4
votes
0
answers
229
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 ...
- 461
11
votes
1
answer
652
views
How to correctly state Cauchy's rigidity theorem?
Cauchy's rigidity theorem is often stated briefly as
Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent.
As a more formal generalization to general ...
- 13.6k
5
votes
0
answers
93
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 ...
- 13.6k
5
votes
2
answers
134
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)\...
- 13.6k
5
votes
0
answers
139
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 $...
- 765
10
votes
3
answers
322
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 ...
- 24.2k
3
votes
1
answer
106
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$ ...
- 19.7k
19
votes
1
answer
928
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 ...
- 13.6k
4
votes
3
answers
347
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 ...
- 13.6k
12
votes
1
answer
428
views
Curve with no embedding in a toric surface
I am looking for a smooth proper curve $C$ such that there does not exist any closed embedding $C \to S$ where $S$ is a (normal projective) toric surface.
Since $C$ is smooth I believe it suffices to ...
- 3,625
7
votes
1
answer
289
views
Separating a lattice simplex from a lattice polytope
Let $P\subset\mathbb{R}^n$ be a convex lattice polytope.
Do there always exist a lattice simplex $\Delta\subset P$ and an affine hyperplane $H\subset\mathbb{R}^n$ separating $\Delta$ from the convex ...
- 8,998
7
votes
0
answers
152
views
Probability of landing inside the convex hull of previously sampled points
Let $\{X_i\}_{0\leq i\leq\infty}$ be i.i.d. random vectors in $\mathbb{R^d}$.
I would like to show that the probability of one point being in the convex hull of the others goes to one with the number ...
- 233
2
votes
0
answers
47
views
Source request: Optimal bounds on signings of points from a convex body
I recently came across an old survey of problems in discrete geometry: https://pdfs.semanticscholar.org/c350/f4d4a9466fa6708d99ec1187c63d89bed20f.pdf
Problem 2.1 from the list caught my eye. It states ...
2
votes
1
answer
191
views
Polytope with most faces
Fix $m,n \in \mathbb{N}$ with $m \ge n+1$. Take $m$ points in general position in $\mathbb{R}^n$ and let $P$ be their convex hull. What is the maximal number of (external, codimension-one) faces that $...
- 465
1
vote
1
answer
184
views
Is the following generalization of the Caratheodory theorem true?
The colorful Carathéodory theorem (Bárány, 1982) considers $d+1$ "colors" $X_1,\ldots,X_{d+1}\subseteq \mathbb{R}^d$, and a point $x$ in the convex hull of each color ($x\in \text{conv}(X_i)$...
- 3,549
2
votes
1
answer
295
views
Are orbit polytopes of rotation subgroup of Coxeter group combinatorially equivalent?
Suppose that $G\subset O(d)$ is a finite reflection (finite Coxeter) group. For any $v\in \mathbb{R}^d$ which is not fixed by any non-trivial $g\in G$, one can consider the orbit polytope (Coxeter) ...
- 439
3
votes
1
answer
159
views
Are cyclic orbitopes of permutahedra necessarily simplicies?
Suppose that $v=(v_1,\ldots, v_d)\in \mathbb{R}^d$ lies in the linear subspace $v_1+\cdots +v_d=0$, and moreover that the coordinates are pairwise distinct. The permutahedron \begin{equation} P(\...
- 439
9
votes
1
answer
262
views
Probability that random high dimensional vectors are all on the convex hull
Say I pick $n$ i.i.d. random standard normal points in $\mathbb{R}^d$. Roughly, as long as $n$ is much smaller than exponential in $d$, with high probability all points will be on the convex hull. ...
- 1,798
1
vote
0
answers
38
views
Structural properties of polytopes for mainstream integer or linear programs
Are there any papers/textbooks/monographs that describe distinguishing properties of the polytopes that arise when solving the linear relaxation of well-known integer programs? For example, it is ...
- 4,049
4
votes
0
answers
82
views
Classification of space-filling (by identical copies) convex polyhedra in R^3
Is the classification of space-filling (by identical copies) convex polyhedra in R^3 is known ?
There are only 5 "parallelohedra" - filling by translation.
But if relax that property to ...
- 24.9k
6
votes
0
answers
381
views
An inequality related to the numbers of faces of polytopes with d+2 facets
I would like to prove an inequality related to the number of $k$-faces of two $d$-polytopes with $d+2$ facets; see (1) below.
Let $r>0$, $s>0$, $t\ge 0$, and $d\ge 2$ be such that $d=r+s+t$. We ...
0
votes
0
answers
109
views
The role of a combination of Eneström-Kakeya and Gauss-Lucas theorems: reference request or soft question, asking for this combination as tool
In past days I was trying to create problems or direct applications invoking Eneström—Kakeya and Gauss-Lucas theorems for certain arithmetic functions that I know from analytic number theory. These ...
4
votes
0
answers
114
views
Can we combine the symmetries of two polytopes to create a more symmetric polytope?
Suppose that there are two combinatorially equivalent (convex) polytopes $P_1,P_2\subset\Bbb R^d$, that is, both with the same face lattice $\mathcal L$.
The symmetry group $\mathrm{Aut}(P_i)\subset\...
- 13.6k
6
votes
1
answer
212
views
A polytope with congruent facets and an insphere that is not facet-transitive?
Is there a $d$-dimensional convex polytope (convex hull of finitely many points, not contained in a proper subspace), with $d\ge 4$ and the following properties?
All facets are congruent,
it has an ...
- 13.6k
9
votes
2
answers
321
views
Is a polytope that has in-spheres for faces of all dimensions already regular?
Let $P\subset\Bbb R^d$ be a convex polytope (convex hull of finitely many points).
A $k$-in-sphere of $P$ is a sphere centered at the origin to which each $k$-face of $P$ is tangent. So a 0-in-sphere ...
- 13.6k
3
votes
1
answer
84
views
Tilings of lattice polytopes by transformations of lattice polytopes
A quasi-lattice polytope is a polytope obtained by reflections, translations, and rotations of lattice polytopes. In a tiling of a lattice polytope by quasi-lattice polytopes, are all quasi-lattice ...
- 745
5
votes
1
answer
361
views
What is known about the duals of cyclic polytopes?
What is known about the duals of cyclic polytopes, in particular, their facets (or equivalently, the vertex-figures of cyclic polytopes)?
In even dimensions, all facets of the dual are ...
- 13.6k
3
votes
1
answer
111
views
Reference for "every 5-dimensional polytope has a 3-gonal or 4-gonal face"
It seems to be folklore that every 5-dimensional convex polytope has a 3-gonal or 4-gonal face of dimension two. I was not able to track down a source for that claim.
Alternatively, I would be ...
- 13.6k
5
votes
2
answers
304
views
Is there a 4-polytope without 3-gonal and 4-gonal faces, other than the 120-cell?
The question is in the title:
Question: Is there any 4-dimensional polytope without 3-gonal and 4-gonal faces (of dimension two), other than the 120-cell?
I consider only convex polytopes (convex ...
- 13.6k
1
vote
0
answers
116
views
Untruncate permutohedron of order 5
I would like to understand commutation classes of reduced expressions of the longest element in $S_5$ a little better. For this, it makes sense to look at the permutohedron of order 5. Since I am only ...
- 1,813
0
votes
0
answers
76
views
Visualization of higher Bruhat order B(5,2)
I made the following images of the higher Bruhat order B(5,2) (in the sense of Manin/Schechtman) with vZome:
image 1
image 2
image 3
Unfortunately, in vZome its not possible do have regular octagons,...
- 1,813
0
votes
0
answers
53
views
Separability of Minkowski Sum of well-behaved sets
Let $A$ and $C$ be non-empty simply connected and connected subsets of $\mathbb{R}^k$ and suppose that $C$ is convex. Then is the Minkowski sum $A+C$ separable?
- 5,405
4
votes
1
answer
200
views
Is there a spherical analogue of polar duality for spherical complexes?
Let $P$ be a spherical complex, which essentially means a tiling of a sphere, let us say the $(d-1)$-dimensional sphere $\mathbb{S}^{d-1}$ in $\mathbb{R}^d$ to fix notation, where each cell is a ...
- 5,215
2
votes
0
answers
103
views
Polytopes with large dihedral angles
The regular $d$-simplex has dihedral angle $\arccos(1/d)<90^\circ$, and the $d$-cube has dihedral angle exactly $90^\circ$.
The maximal dihedral angle of a prism over a $(d-1)$-simplex is also $90^\...
- 13.6k
2
votes
0
answers
53
views
Can a polytope with vertex-transitive edge graph or face lattice be made vertex-transitive?
Let $P\subset\Bbb R^d$ be a convex, full-dimensional polytope (convex hull of finitely many points, affine hull is the whole space), $G_P$ its edge graph and $\mathcal F_P$ its face lattice. Any of ...
- 13.6k
3
votes
0
answers
115
views
Pyramids whose volume can be computed by simple cutting and glueing
Since this question remained without answers even after a bounty, I thought it might be time to ask it here.
For which pyramid can you compute the volume from simple cut-and-glue processes? The Dehn ...
- 4,432
3
votes
0
answers
86
views
An exponential integral over a closed convex polytope
For any $T\geq 2$, let us define the polyhedron $S$ given by
\begin{align*}
S:=\{\underline{t}:=(t_0,t_1,t_{2},t_{3},t_{4},t_{5},t_{6},t_{7})\in [0,+\infty)^{8}:A\underline{t}\leq (\log T)\textbf{1}\}
...
7
votes
1
answer
317
views
Minimum area of the convex hull of the union of a parallelogram and a triangle
This question is somewhat dual to my previously stated question about Maximum area of the intersection of a parallelogram and a triangle, where the triangle and parallelogram each is assumed to be of ...
- 7,276
1
vote
0
answers
62
views
fast V representation update of polytope
Say that I have both the V and the H representation of a (possibly unbounded) polytope $P$. I want to append a some rows to the H representation, how can I quickly update the V representation to ...
- 155