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
5
votes
0
answers
474
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 ...
- 10.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 ...
- 13.6k
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
2
votes
1
answer
124
views
Polytopes and polyhedral cones in complex Euclidean space
Given $A \in \mathsf{M}_{m \times n}(\mathbb{R})$ and $b \in \mathbb{R}^m$, the polyhedron with respect to $A$ and $b$, denoted by $P(A,b)$, is defined by
$$ \{ x \in \mathbb{R}^n \mid Ax \le b \}.$$
...
- 1,719
11
votes
2
answers
576
views
Book on the tetrahedron
Does anybody know of a book containing "all you want to know about the tetrahedron"? What you want to know should include basic geometry of the tetrahedron, study of orthocentric tetrahedra, the Monge ...
- 4,492
3
votes
1
answer
94
views
Regular triangulations of star-convex polyhedra with given boundary
Given an $n$-dimensional star-convex polyhedron $P\subset \mathbb{R}^n$ with simplicial facets, is it always possible to construct a regular triangulation $K$ of $P$ which does not subdivide the ...
- 165
1
vote
1
answer
99
views
Estimating volume of a simple object
Volume computation is $\#P$ hard.
Take the $[0,1]^n$ polytope.
Slice it by an half space inequality with $poly(n)$ bit rational coefficients into two unequal halves.
Volume of bigger section is $\...
- 13.9k
4
votes
1
answer
4k
views
H-representation versus V-representation of polytopes
The H-representation of a convex polytope $S$, is just a set of linear inequalities corresponding to the intersection of halfspaces:
$S = ( x | Ax\leq b )$.
One could also represent a convex polytope ...
- 45
2
votes
1
answer
340
views
Bit complexity of Barvinok's algorithm
I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension.
What exactly is this arithmetic complexity?
...
- 13.9k
5
votes
2
answers
755
views
Intersecting a convex polytope with the unit sphere
I have a list of $m$ affine inequalities in $n$ variables of the following form
$$a_1 x_1 + \cdots + a_n x_n \leq c_n$$
I would like to know whether there is any point on the unit sphere in $\...
user47305
10
votes
2
answers
523
views
When does every point in a polytope lie along a chord between its edges?
Consider the 3-simplex, or tetrahedron, in 3-space. Regardless of the positions of the vertices, every point in the simplex lies on a chord between two non-adjacent edges of the simplex. Or, ...
- 329
2
votes
1
answer
349
views
Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?
Sorry the title may be unclear. I do not know how to give it a good title.....
Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
- 159
6
votes
2
answers
154
views
Inequality on permutation polytope
Let $a = (a_1, \cdots, a_n), b = (b_1, \cdots, b_n), c = (c_1, \cdots, c_n) \in \mathbb{R}^n$ with $a_1 \geq \cdots \geq a_n, b_1 \geq \cdots \geq b_n, 0 < c_1 \leq \cdots \leq c_n$.
In addition, ...
- 61
6
votes
3
answers
355
views
Basic question about polytope duals
The following must be well known. Is there a beginning or midlevel
text where the answer is discussed? Thanks.
Along with a polytope one has the notion of its dual which is officially
defined via ...
- 1,411
3
votes
0
answers
52
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 ...
- 31
11
votes
1
answer
609
views
Tighter Caratheodory on the moment curve?
The moment curve is the set of points of the form
$$(t,t^2,t^3,...,t^n) \in R^n$$
Let $M$ be the portion of the moment curve where $t\in [0,1]$, and let $\overline{M}$ be the convex hull of $M$.
...
- 3,979
18
votes
2
answers
986
views
"Derived" polyhedra and polytopes
The notion of derived polygon is natural and leads to remarkable convergence.
Start with a polygon, and replace it by locating a point on every edge
a fraction $\alpha$ between the two endpoints. For ...
- 151k
1
vote
0
answers
113
views
Two Questions on Tetrahedra and Platonic Solids [closed]
As was known to the ancients, two congruent regular tetrahedra can be inscribed in a cube and likewise 5 congruent regular tetrahedra can be inscribed in a regular dodecahedron. Is the converse to ...
- 157
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
6
votes
2
answers
638
views
Alexander's theorem (on stellar moves)
A widely used theorem these days says that given (abstract) simplicial complexes $K$ and $K'$, a polyhedron $P\subset R^n$ and homeomorphisms $|K|\to P$ and $|K'| \to P$ which are linear (better to ...
1
vote
1
answer
125
views
Projections of particular simplex yielding boundary of a regular polygon?
What is the maximum $m$ such that there is a simplex with $n$ vertex points in $n-1$ dimensions whose projection yields boundary of a regular $m$-gon on $2D$ plane?
- 1,826
12
votes
4
answers
2k
views
What is the number of equitriangulations of the n-cube?
I wonder if this question has been considered before and if anything is known. My search attempts have failed so far.
Let's consider the n-dimesnional cube, $[0,1]^n$, and let's call a simplex with ...
- 85.6k
6
votes
2
answers
643
views
A convex polyhedral analog of the pentagram map
I am wondering if there is a three-dimensional analog of
the pentagram map, which maps a convex polygon to another
convex polygon. Here's the Wikipedia image:
I am seeking something similar that maps ...
- 151k
2
votes
1
answer
140
views
Separation of two pointed polyhedral cones using hyperplanes generated by facets
Let $C_1$ and $C_2$ two pointed (that is, with vertex in $0$) polyhedral cones in $\mathbb{R}^n$ with $\dim(C_1)=\dim(C_2)=n$. If
$$\mbox{relative interior}(C_1)\cap \mbox{relative interior}(C_2)=\...
- 131
2
votes
0
answers
87
views
Iterated polyhedron face twisting
Let $Q$ be a polygon in the plane. Modify $Q$ by rotating each edge about its
midpoint by $180^\circ$. The result is $Q$ again: No change.
This suggests exploring a similar operation in $\mathbb{R}^3$...
- 151k
11
votes
2
answers
2k
views
How many non-equivalent sections of a regular 7-simplex?
Suppose we have a regular 7-simplex in $\mathbb{R}^8$ defined by vertices <1,0,0,...,0>, <0,1,0,..,0>,...,<0,...,0,1>. A section is a 3-dimensional linear subspace of $\mathbb{R}^8$ that ...
3
votes
1
answer
263
views
Size of a minimal non-negative conic basis
Suppose $v_1,\dots,v_n \in \mathbb{R}^k$ are entry-wise non-negative (column) vectors with $k<n$. Let $r \leq k$ be the non-negative rank of the matrix $V = [v_1 v_2 \cdots v_n]$ (i.e., the ...
5
votes
0
answers
140
views
$q$-Kostant partition function and flow polytopes?
The Kostant partition function is known to be related to volumes and Ehrhart polynomials of flow polytopes of graphs (see e.g. https://link.springer.com/article/10.1007/s00031-008-9019-8 or https://...
- 24.2k
9
votes
1
answer
240
views
Cyclic polygons generalized to higher dimensions
Many theorems hold for cyclic polygons—convex polygons inscribed
in a circle. Perhaps the most basic is this,
from the reference cited below:
Theorem. There exists a cyclic polygon of $n \ge ...
- 151k
0
votes
1
answer
117
views
Closed form solutions for maximal subsets of convex polytopes
I'm looking for any known exact results about inscribing simple convex bodies inside a convex polytope. The most famous is the Löwner-John ellipsoid, but as far as I understood in general there is no ...
- 445
8
votes
2
answers
285
views
$f$-vector of simple convex polytope via directions of facets
Let $P$ be a simple convex polytope in $\mathbb{R}^d$ (that is, any vertex belongs to exactly $d+1$ facets). Given the collection of outer normals to facets of $P$, combinatorics of $P$ may be ...
- 109k
2
votes
2
answers
624
views
Secondary Polytope Simplicial?
Is the secondary polytope of a simplicial polytope necessarily simplicial?
- 360
6
votes
1
answer
254
views
Extend space to make polyhedra convex hulls of finite sets
A (convex) polytope is the convex hull of a finite number of points in Euclidean space (this is the so-called "vertex description"). Alternatively, it can defined to be a bounded polyhedron (this is ...
- 24.2k
5
votes
0
answers
129
views
Lattice paths in polytopes
Let $P$ be a polytope in $\mathbb{R}^n$. Let $A_ix = b_i$ be the defining equations of its codimension $1$ faces. Is there an algorithm or some kind of criterion to decide if the lattice points inside ...
- 501
1
vote
0
answers
94
views
Family of polytopes whose measure respects multiplication?
Is there a family $\mathcal{P}$ of integral polytopes and a polytope product $\star$ such that for every $n\in\mathbb N_{>1}$ $\exists p\in\mathcal{P}:vol(p)=n$ and
$\forall q\in\mathcal{P}\...
- 13.9k
8
votes
1
answer
498
views
Loday's characterization and enumeration of faces of associahedra (Stasheff polytopes)
From "The multiple facets of the associahedra" by Loday:
Let us consider the formal power series
$$f(x) = x+a_1 x^2 +a_2 x^3 + \cdots+ a_n x^{n+1} + \cdots$$
and let
$$ g(x) = x+b_1 x^2 + ...
- 10.5k
6
votes
1
answer
727
views
Regular unimodular triangulation for a certain simplex
Consider an $n$-simplex with vertices given by
$(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers,
and $i=0,1,\dots,n+1$.
Does this simplex admit a regular, ...
- 15.8k
1
vote
0
answers
97
views
Formula for exponential integral over a cone
While reading 'Computing the Volume, Counting Integral points, and Exponential Sums' by A. Barvinok (1993), I came across the following:
"Moreover, let $K$ be the conic hull of linearly independent ...
- 81
1
vote
1
answer
106
views
Linear relations between volume of a polytope and its faces
Let $P$ be a polytope. Is anything known about the set of linear relations that hold between the volumes of the (not-necessarily proper) faces of $P$ as $P$ “varies slightly”? By varies slightly I ...
- 3,079
29
votes
0
answers
3k
views
Why do polytopes pop up in Lagrange inversion?
I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
1
vote
1
answer
256
views
Quick way to compute Ehrhart polynomial of Young diagram posets?
Using the hook formula, it is easy to compute the volume of order polytopes obtained from posets with partition shape, since this is the same as the number of linear extensions.
To my knowledge, ...
- 15.8k
12
votes
1
answer
614
views
Covering the unit sphere by open hemispheres
Suppose $H_1,\ldots,H_{2n}$ are open hemispheres which cover $S^{n-1}$ with the property that removing any one of them leaves $S^{n-1}$ uncovered. Is it necessarily the case that the hemispheres can ...
- 219
1
vote
0
answers
67
views
Is there a simple polyhedral characterization of these integral points?
Given $n\in\mathbb Z_{>0}$ consider the set of $n$-tuples $$(a_1,\dots,a_n)\in\mathbb Z_{\geq0}^n$$ on following simple conditions
$0\leq a_i\leq 2^{2^n}-1$
If $a_i=b_{i,2^{n}-1}2^{2^{n}-1}+\dots+...
- 13.9k
1
vote
0
answers
120
views
John's ellipsoid of a polytope
Suppose that $X$ is $\mathbb R^n$ with some polyhedral norm, that is, the unit ball of $X$ is an $n$-dimensional polytope. Assume that the John ellipsoid of $X$ is an Euclidean ball that touches every ...
- 113
1
vote
0
answers
52
views
How does one translate from convex hull to a set of facets (inequalities)? [duplicate]
Suppose I have defined a convex set as the convex hull of a set of points. (I know that all these points are "extremal points" of the convex set.) I know want to translate this description of the ...
- 11
1
vote
0
answers
99
views
Finding a point on a convex set
Given a compact bounded convex set $\mathcal C\subseteq\mathbb R^n$ given by $t$ hyperplane inequalities I want to find a point $u\in\mathcal C$ such that for all $v\in\mathcal C$
a convex relation $...
- 1,826
4
votes
1
answer
388
views
What are the 4 convex simplicial 4-polytopes that have 6 vertices?
In Convex polytopes and related complexes by Klee and Kleinschmidt they state the number of $d$-polytopes with $d+2$ vertices is $\lfloor \frac{d^2}{4}\rfloor$.
I was wondering what the four $4$-...
- 43
1
vote
0
answers
37
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,...
- 13.2k
4
votes
0
answers
147
views
Name for facet of a cone containing all but one edge
Let $C \subseteq \mathbb R^n$ be a polyhedral cone, so generated by its edges ($1$-dimensional faces) and $F \subseteq C$ a facet (codimension $1$ face) of it containing every edge except $e$. In ...
- 27.9k
6
votes
1
answer
254
views
Triangulations of convex surfaces
Let $M$ be a smooth closed positively curved surface in Euclidean 3-space, $T$ be a geodesic triangulation of $M$, and $E$ be the edge graph of the convex hull of vertices of $T$.
It is easy to see ...
- 7,194