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

Filter by
Sorted by
Tagged with
2 votes
0 answers
45 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 ...
Arun Jambulapati's user avatar
2 votes
1 answer
164 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 $...
zjs's user avatar
  • 465
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)$...
Erel Segal-Halevi's user avatar
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) ...
Bob's user avatar
  • 439
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(\...
Bob's user avatar
  • 439
9 votes
1 answer
213 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. ...
Geoffrey Irving's user avatar
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 ...
Tom Solberg's user avatar
  • 3,929
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 ...
Alexander Chervov's user avatar
6 votes
0 answers
316 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 ...
Guillermo Pineda-Villavicencio's user avatar
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 ...
user142929's user avatar
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\...
M. Winter's user avatar
  • 12.5k
6 votes
1 answer
200 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 ...
M. Winter's user avatar
  • 12.5k
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 ...
M. Winter's user avatar
  • 12.5k
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 ...
Display name's user avatar
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 ...
M. Winter's user avatar
  • 12.5k
3 votes
1 answer
109 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 ...
M. Winter's user avatar
  • 12.5k
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 ...
M. Winter's user avatar
  • 12.5k
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 ...
Bipolar Minds's user avatar
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,...
Bipolar Minds's user avatar
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?
ABIM's user avatar
  • 5,019
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 ...
Malkoun's user avatar
  • 4,991
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^\...
M. Winter's user avatar
  • 12.5k
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 ...
M. Winter's user avatar
  • 12.5k
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 ...
ARG's user avatar
  • 4,342
3 votes
0 answers
83 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}\} ...
The Number Theorist's user avatar
7 votes
1 answer
312 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 ...
Wlodek Kuperberg's user avatar
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 ...
user39430's user avatar
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)$ ...
skr's user avatar
  • 512
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 ...
Frederik vom Ende's user avatar
1 vote
0 answers
150 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 ...
KTree's user avatar
  • 11
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,...
Manfred Weis's user avatar
  • 12.6k
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 ...
Min Wu's user avatar
  • 461
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 ...
jnhnum1's user avatar
  • 31
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$ ...
Guillermo Pineda-Villavicencio's user avatar
2 votes
1 answer
777 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 ...
Davide Papapicco's user avatar
2 votes
1 answer
218 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-...
Davide Papapicco's user avatar
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\}$...
bucket's user avatar
  • 85
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 ...
Ruy's user avatar
  • 2,233
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 ...
M. Winter's user avatar
  • 12.5k
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) $\...
Fred's user avatar
  • 157
4 votes
2 answers
476 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 ...
Dr. Richard Klitzing's user avatar
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 $\...
Manfred Weis's user avatar
  • 12.6k
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 ...
M. Winter's user avatar
  • 12.5k
2 votes
1 answer
149 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 (...
gkgktata's user avatar
4 votes
0 answers
345 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(\...
James Silipo's user avatar
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*}$ ...
BrianT's user avatar
  • 1,197
7 votes
2 answers
495 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 = \...
alesia's user avatar
  • 2,582
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\...
Lemma1's user avatar
  • 157
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: ...
Jonathan Fine's user avatar
5 votes
1 answer
404 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 ...
Tom Copeland's user avatar
  • 9,937

1
3 4
5
6 7
19