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
1
answer
113
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)$ ...
- 512
7
votes
1
answer
299
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
179
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 ...
- 11
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
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 ...
- 461
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
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
871
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
237
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
27
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\}$...
- 85
10
votes
1
answer
542
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 ...
- 2,263
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 ...
- 13.6k
3
votes
1
answer
93
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) $\...
- 157
4
votes
2
answers
494
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
92
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 $\...
- 13.2k
31
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 ...
- 13.6k
2
votes
1
answer
153
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 (...
- 23
4
votes
0
answers
367
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(\...
- 311
3
votes
0
answers
115
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*}$ ...
- 1,227
7
votes
2
answers
552
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 = \...
- 2,772
1
vote
1
answer
112
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\...
- 157
2
votes
0
answers
94
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: ...
- 459
6
votes
1
answer
539
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 ...
- 10.5k
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,462
1
vote
0
answers
43
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 ...
- 523
2
votes
1
answer
96
views
A matrix that commutes with all symmetries of a vertex-transitive polytope
Let $P\subset\Bbb R^d$ be a vertex-transitive polytope aka. an orbit polytope.
Can there be a matrix $T\in\mathrm{SO}(\Bbb R^d)$ that commutes with all symmetries in $\mathrm{Aut}(P)\subset\mathrm O(\...
- 13.6k
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
5
votes
1
answer
462
views
Polynomial size embeddings of toric varieties from polytopes?
Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan.
$X_P$ is always projective, because the collection of characters corresponding to the points $\...
- 1,462
0
votes
1
answer
296
views
Overlap count of convex combination of points [closed]
Let $x_1, ..., x_n\in\mathbb{R}^d$. We know that a point $x$ in the convex hull $\text{conv}(x_1, ..., x_n)$ may be expressed as convex combinations $x=\sum_{i=1}^n r_ix_i=\sum_{i=1}^n s_ix_i$ with ...
- 461
4
votes
3
answers
617
views
An example of a "simple poset" which does not belong to a convex polytope
Are there examples of d-regular graphs (i.e. graphs where every node has exactly d adjacent nodes) which are not the 1-skeleton of a simple convex polytope?
UPDATE:
New version of the question: is ...
- 1,435
5
votes
1
answer
280
views
Classification of vertex-transitive zonotopes
Zonotopes are convex polytopes that can be defined in several equivalent ways:
parallel projections of cubes,
Minkowsi sums of line segments,
only centrally symmetric faces,
...
I wonder whether ...
- 13.6k
4
votes
2
answers
173
views
4-polytopes with only one kind of regular facet
Is there a neat way to show (or a reference that already proves) that
the 4-cube is the only convex 4-polytope in which all facets are regular 3-cubes?
the 24-cell is the only convex 4-polytope in ...
- 13.6k
3
votes
1
answer
152
views
Are there any more polytopes whose 2-faces are identical 4-gons?
What are examples for convex polytope $P\subset \Bbb R^d,d\ge 3$ for which holds
$P$ is 2-face transitive (that is, all 2-faces are equivalent under the symmetries of $P$), and
all 2-faces of $P$ are ...
- 13.6k
7
votes
1
answer
483
views
Furthest distance half the diameter?
Let $S$ be the surface of a convex body, polyhedral or smooth,
embedded in $\mathbb{R}^3$.
For a point $x \in S$, let $F(x)$ be the set of furthest points
from $x$, measured by shortest paths on the ...
- 151k
5
votes
1
answer
417
views
Iterated derivative and rectangular standard Young tableaux
We first make a few definitions, seemingly out of the blue (they are introduced/defined in this paper).
Let $F^0_{a}(z) = (1-z)^{-1}$ and define recursively
$$
F^{k+1}_{a}(z) = z^{a-1} \frac{d^a}{dz^...
- 15.8k
6
votes
1
answer
697
views
How wide is the Birkhoff Polytope?
This question is migrated from MSE where it turned out to be much harder than I thought. I still cannot figure this out. Does anyone have any ideas?
Define the width of a polytope $P \subset \mathbb ...
- 1,955
3
votes
0
answers
264
views
Guises of the refined Eulerian numbers, generated by tangent vectors (OEIS A145271)
The Eulerian numbers (OEIS A008292, not to be confused with the Euler numbers) pop up in numerous scenarios in combinatorics and advanced analysis, one as the components of the h-vectors of the ...
- 10.5k
3
votes
1
answer
326
views
How can the same polytope have three different volumes? [closed]
I'm quite new to geometry and I came across the idea that the same convex polytope can have at least three different volumes.
Consider the permutohedron, formed by the convex hull of the n! points ...
- 163
1
vote
0
answers
248
views
Gaussian mean width of normal random cones
Suppose $1 \leq n < m < \infty$ are integers. For $g \sim \mathcal N(0, I_n)$ define the gaussian mean width of a non-empty set $T \subseteq \mathbb R^n$ by
$$
w(T) := \mathbb E \sup_{x \in T} \...
- 119
1
vote
0
answers
39
views
Partition complexity measure of the boolean cube?
Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the ...
- 13.9k
8
votes
3
answers
390
views
Is there any edge- but not vertex-transitive polytope in $d\ge 4$ dimensions?
I consider convex polytopes $P\subset\Bbb R^d$. The polytope is called vertex- resp. edge-transitive, if any vertex resp. edge can be mapped to any other by a symmetry of the polytope.
I am looking ...
- 13.6k
1
vote
0
answers
49
views
Realizing 0/1-polytopes with shortest possible edge lengths
Has there been something written about the following question?
Question: Given a 0/1-polytope, what is the shortest edge lengths with which this polytope can be realized as a 0/1-polytope.
The ...
- 13.6k
1
vote
1
answer
103
views
A source for $01$-polytopes
Can you recommend any books or survey articles on $01$-polytopes, thats is, polytopes with vertices in $\{0,1\}^n$?
I am less interested in random $01$-polytopes, but more in the combinatorial ...
- 13.6k
2
votes
1
answer
85
views
The number of Hamiltonian circuits on a convex polytope embedded in $\mathbb{R}^N$
Recently I wondered whether there might be a natural topological complexity measure for convex polytopes embedded in $\mathbb{R}^N$. After some reflection it occurred to me that the number of distinct ...
- 3,871
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
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
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
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
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
6
votes
1
answer
337
views
Edges of the contact polytope of the Leech lattice
Let $P\subset\Bbb R^{24}$ be the contact polytope of the Leech lattice, that is, $P$ is the convex hull of the 196,560 shortest vectors of $\Lambda_{24}$.
Question: What are the edges of $P$?
Let'...
- 13.6k