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
916
questions
1
vote
1
answer
174
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)$...
2
votes
1
answer
285
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) ...
3
votes
1
answer
156
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(\...
9
votes
1
answer
212
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
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
votes
0
answers
79
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 ...
6
votes
0
answers
313
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
106
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
113
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\...
6
votes
1
answer
198
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 ...
9
votes
2
answers
306
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 ...
3
votes
1
answer
77
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 ...
5
votes
1
answer
314
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 ...
3
votes
1
answer
108
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 ...
5
votes
2
answers
301
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 ...
1
vote
0
answers
103
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 ...
0
votes
0
answers
72
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,...
0
votes
0
answers
52
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?
4
votes
1
answer
183
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 ...
2
votes
0
answers
98
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^\...
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 ...
3
votes
0
answers
112
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 ...
3
votes
0
answers
82
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
310
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 ...
1
vote
0
answers
51
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 ...
2
votes
1
answer
105
views
Coordinate-symmetric convex polytopes with equal Erhart (quasi)-polynomials
Recall that given a nondegenerate polytope $P \subset \mathbb{R}^n$ which is the convex set of some vectors with integral coordinates, the Erhart polynomial $p_P(t)$ a polynomial such that $p_P(t)$ ...
7
votes
1
answer
263
views
Lipschitz-continuity of convex polytopes under the Hausdorff metric
Recently, I proved the following Lipschitz-continuity like result for convex polytopes:
Let $A\in\mathbb R^{m\times n}$ and $b,b'\in\mathbb R^m$ be given such that $\{x\,:\,Ax\leq 0\}=\{0\}$ (which ...
1
vote
0
answers
149
views
Regular triangulation of hypercube
I have started studying regular subdivisions of the $n$-cube, and came across the following post: Regularity of Delaunay triangulation of a hypercube.
My question is whether the "standard ...
1
vote
0
answers
36
views
Definition of convex hulls via maximal sets of interior-disjoint simplices
Let the simplex cover of a finite set $\mathcal{P}\subset \mathbb{E}^n,\ n\,\le\, k:=\operatorname{card}(\mathcal{P})\,\lt\infty$ of points in Euclidean $n$-space of which no $n+1$ are co-hyperplanar,...
10
votes
3
answers
1k
views
Number of regions formed by $n$ points in general position
Given $n$ points in $\mathbb{R}^d$ in general position, where $n\geq d+1$. For every $d$ points, form the hyperplane defined by these $d$ points. These hyperplanes cut $\mathbb{R}^d$ into several ...
3
votes
0
answers
51
views
Deformations that flatten small curvature
I'm trying to show that any 3-dimensional polyhedron with many vertices can be mildly deformed so that its vertices are no longer convexly independent. I suspect it suffices to look at a vertex with ...
3
votes
0
answers
70
views
On the proportion of simplicial $d$-polytopes on $n$-vertices
I have a question regarding estimates for the proportion of simplicial $d$-polytopes on $n$-vertices.
Let $c_s(n,d)$ denote the number of combinatorial types of simplicial $d$-polytopes on $n$ ...
2
votes
1
answer
773
views
Interior point of a convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
2
votes
1
answer
217
views
Sampling algorithms on convex polytopes
Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...
0
votes
0
answers
26
views
How do you refer to the feasible set of solutions to a mixed-integer program?
I frequently want to refer to the feasible set of solutions to a mixed integer programming instance. Is there a name for a subset of $\mathbb{R}^n\times\{0,1\}^m$ of the form $\{(x,a)| Ax + Ba\leq b\}$...
10
votes
1
answer
531
views
What is the convex hull of the quaternionic symmetries of the 3 dimensional cube?
It is well known that there are exactly five 3-dimensional regular convex polyhedra, known as the Platonic solids.
In 1852 the Swiss mathematician Ludwig Schlafli found that there are exactly six ...
17
votes
4
answers
1k
views
Can I build infinitely many polytopes from only finitely many prescribed facets?
Given a finite set of convex $d$-dimensional polytopes $\mathcal P$, for some $d\ge 2$.
Question: Is it true that there are only finitely many different convex $(d+1)$-dimensional polytopes whose ...
3
votes
1
answer
92
views
Affine equivalence of Coxeter permutahedra?
Suppose that $W=\langle s_1,\ldots, s_d\mid (s_is_j)^{m_{ij}}=e\rangle$ is a finite reflection group and consider its standard $d$-dimensional geometric realization (i.e., the Tits representation) $\...
4
votes
2
answers
475
views
addition theorems for hypersine
I learned from Wolfram MathWorld about hypersine, as being a dimensional analog trig function for hypersolid angles. There it is being defined by
The hypersine ($n$-dimensional sine function) is a ...
1
vote
1
answer
90
views
Convexity of the Voronoi cells of higher-dimensional polyhedra
let a convex polytope $\mathcal{P}$ in $E^n$ be defined as in the tag-description with the additional requirement that their volume be strictly positive.
let further the Voronoi Cells $VC(f)$ of $\...
29
votes
7
answers
3k
views
Why are we interested in permutahedra, associahedra, cyclohedra, ...?
The following families of polytopes have received a lot of attention:
permutahedra,
associahedra,
cyclohedra,
...
My question is simple: Why?
As I understand, at least the latter two were ...
2
votes
1
answer
148
views
Number of orthants intersected by a convex hull
I'm trying to figure out the following problem:
Let $x_1,\ldots,x_k\in\mathbb{R}^n$ be some points for some $k<n$. Let $\mbox{conv} (x_1,\ldots,x_k)$ be their convex hull. I'm looking for a tight (...
4
votes
0
answers
342
views
On intrinsic volumes
Let $\Gamma$ be a convex polytope in $\mathbb R^n$. The $k$-th intrinsic volume of $\Gamma$ is the number
$$
\text{v}_k(\Gamma)=\sum_{\Delta\in{\mathcal B}(\Gamma,k)}\text{vol}_k(\Delta)\psi_\Gamma(\...
3
votes
0
answers
113
views
On two different descriptions of Delzant polytopes
I have seen two different ways of describing a Delzant polytope:
From Canna Da Silva https://people.math.ethz.ch/~acannas/Papers/toric.pdf, a Delzant polytope is a polytope in $\mathbb{R}^{n*}$ ...
7
votes
2
answers
494
views
Cut norm versus $l_1$ norm
Let $K$ be the set of $n\times n$ matrices with zero diagonal entries and such that the sum of all entries is zero.
The cut norm of a $n\times n$ matrix $M$ is:
$$
cut(M) = \sup_{S, T, S\cap T = \...
1
vote
1
answer
103
views
Regions of hyperplane arrangements and their faces
Consider a finite hyperplane arrangement $\mathcal{A}$ over $\mathbb{R}^n$. Let the regions given by $\mathcal{A}$ be $\mathcal{R}(\mathcal{A})=\{A_1,\dots A_m\}$ for some $m$.
For any index set $I\...
2
votes
0
answers
93
views
Anything similar to cone product formula (for convex polytopes)?
The convex polytope flag vector ring $\mathcal{R}$ satisfies the cone product formula
$$
C(U) C(V) = C(J(U, V)) + DUV
$$
where
$$
J(U, V) = U C(V) + C(U) V - e_1 UV
$$
is the join formula.
Note: ...
5
votes
1
answer
398
views
Proofs of Euler's characteristic formula for n-Dim polytopes
Twenty proofs of Euler's formula V - E + F - 1 = 1, which applies to convex polyhedrons, i.e., 3-dimensional polytopes, are presented at the Geometry Junkyard.
I'm interested in proofs of the more ...
3
votes
0
answers
86
views
Reference on the faces of the circulation polytope
On page 4 of Generating all vertices of a polyhedron is hard it is mentioned that the facial structure of the circulation polyhedron* is well understood. I am trying to find a reference for this.
I ...
1
vote
0
answers
39
views
Vertex enumeration for polytope with a sparse halfplane description?
Say I have a (bounded convex) polytope $P\subset\mathbb R^d$ with description $Ax\le b$, where $A$ is sparse in the sense that there are at most $k$ nonzero entries in each row or column, where $k$ is ...