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
17
votes
3
answers
2k
views
Optimal 8-vertex isoperimetric polyhedron?
I know from Marcel Berger's
Geometry Revealed:
A Jacob's Ladder to Modern Higher Geometry
(p.531)
that it is not yet established which polyhedron in $\mathbb{R}^3$ on 8 vertices achieves the optimal ...
- 151k
3
votes
1
answer
336
views
Cohomology ring of a hypersurface in toric variety
Let $X^n$ be a smooth projective toric variety corresponding to a simple polytope $P$. It is well known that the cohomology ring $H^*(X)$ can be described in terms of combinatorics of faces of $P$.
...
- 21.8k
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
10
votes
1
answer
3k
views
Computionally efficient vertex enumeration for (convex) polytopes
Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...
- 321
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
20
votes
5
answers
1k
views
From convex polytopes to toric varieties: the constructions of Davis and Januszkiewicz
One of the most useful tools in the study of convex polytopes is to move from polytopes (through their fans) to toric varieties and see how properties of the associated toric variety reflects back on ...
- 24.7k
26
votes
7
answers
10k
views
Uniformly Sampling from Convex Polytopes
How to choose a point uniformly from a convex polytope $P \subset [0,1]^n$ defined by some inequalities, $Ax < b$? (Here $A$ is an $m \times n$ matrix, $x \in \mathbb{R}^n$, and $b \in \mathbb{R}^...
- 22.8k
1
vote
1
answer
1k
views
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
- 11
19
votes
3
answers
2k
views
Guises of the Stasheff polytopes, associahedra for the Coxeter $A_n$ root system?
Richard Stanley keeps a famous running compilation of different guises of the celebrated Catalan numbers. The number of vertices of the associahedron is one instantiation among the multitude, and the ...
- 10.5k
16
votes
5
answers
1k
views
A characterization of convexity
While doing some research on polytopes I came to the following question. Maybe it's already somewhere but anyway I'll post it here.
Let $X\subset \mathbb{R}^3$ be such that, for every plane $P$, $P\...
- 1,001
8
votes
2
answers
1k
views
Is every polytope combinatorially equivalent to the intersection of a simplex and a linear subspace?
I wonder whether such a result is known, and if so, whether the proof is trivial.
By polytope I mean the convex hull of finitely many points in $\Bbb R^n$. Assume the simplex to be symmetric and ...
- 13.6k
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 ...
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
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
4
votes
1
answer
74
views
Simplicial polytope with regular cones
Let $P$ be a convex simplicial polytope in $\mathbb{R}^n$. Can we find a convex simplicial polytope $P_0$ in $\mathbb{R}^n$ combinatorially equivalent to $P$, satisfying the following condition: The ...
- 405
0
votes
0
answers
118
views
Weak derivative of projection onto probabilist's simplex
Let $\Delta_n:=\{x\in [0,1]^n:\boldsymbol{1}^{\top}x=1\}$ denote the probabilist's $n$-simplex and let $P:\mathbb{R}^n\rightarrow\Delta_n$ denote the (Euclidean) metric projection onto this simplex ...
- 5,405
8
votes
2
answers
392
views
Can two non-equivalent polytopes of same dimension have the same graph?
By a polytope I mean the convex hull of finitely many points. The graph of a polytope is the graph isomorphic to its 1-skeleton. By equivalence of polytopes I mean combinatorial equivalence, i.e. ...
- 13.6k
0
votes
0
answers
74
views
Diameter of inner parallel body
Let's say I have a convex polytope $\mathcal{P} \subset \mathbb{R}^n$ with non-empty interior.
Let $\mathcal{P}=\bigcap_{i=1}^mH_i$ for some halfspaces $H_i$ and let $d=diam(\mathcal{P})=\sup\{\|x-y\|:...
- 93
18
votes
4
answers
802
views
Volume of convex lattice polytopes with one interior lattice point
Let $P$ be a convex polytope in $\mathbb{R}^3$ whose every vertex lies in the $\mathbb{Z}^3$ lattice.
Question: If $P$ contains exactly one lattice point in its interior, what is the maximum possible ...
- 7,276
0
votes
1
answer
176
views
Maximum vertex amount of low-dimensional simplex projection
Consider an arbitrary simplex $\mathcal{S} \subseteq \mathbb{R}^n$ ($\mathcal{S}$ is a polytope in $\mathbb{R}^n$ with $n+1$ vertices and non-empty interior). Let ${\bf P} \in \mathbb{R}^{m \times n}, ...
- 235
22
votes
5
answers
1k
views
Is the diameter of a centrally symmetric convex body realized by a pair of antipodal points?
Let $S \subset \mathbb{R}^n$ be the boundary of a centrally symmetric convex body and provide $S$ with the geodesic metric given by its embedding in Euclidean space (i.e., the distance between two ...
- 1,303
1
vote
1
answer
139
views
The relationship between facets of an inscribed polytope and those facets' shadows
I posted this question thinking that the response would be two or three answers that say "Counterexamples to this are found in every textbook—for example this one and this one and this one." ...
16
votes
1
answer
743
views
Inequalities for marginals of distribution on hyperplane
Let $H = \{ (a,b,c) \in \mathbb{Z}_{\geq 0}^3 : a+b+c=n \}$. If we have a probability distribution on $H$, we can take its marginals onto the $a$, $b$ and $c$ variables and obtain three probability ...
- 156k
6
votes
2
answers
185
views
Partitions of convex planar regions into zonogons
A zonogon is a centrally symmetric convex polygon.
Are there convex non-zonogons that can be partitioned into a finite number of (convex) zonogons?
Same as 1 with the pieces allowed to be nonconvex ...
- 5,979
1
vote
0
answers
58
views
Are cells of 4-polytopes a convex polyhedron by definition?
I'm going by the Wikipedia definition for a 4-polytope.
Do by definition, cells of 4-polytopes have to be a convex polyhedra?
If not, then are there polyhedra with non-convex faces?
If yes, is it the ...
- 11
9
votes
3
answers
461
views
Minimal combinatorial data needed to define a polytope [duplicate]
Suppose I give a list of vertices $(v_1, v_2, ..., v_n)$, and a list of "adjacencies", i.e. pairs of vertices $(v_i,v_j)$. Does it exists a unique polytope that has this vertices and realises the ...
- 1,435
7
votes
2
answers
909
views
Formula for volume of a convex polytope
So I've been searching around the internet for some answers to this, but I currently have a set of linear constraints: $Ax = b, Cx \le d$ for matrices $A \in \mathbb{R}^{n \times m}$, $b\in \mathbb{R}^...
- 81
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
0
votes
0
answers
98
views
Possible new convex uniform polytope
Does there exist a convex uniform 9-polytope obtained by diminishing the 9-hypercube, removing 480 of its 512 vertices and turning each 8-hypercube facet into an 8-orthoplex?
- 2,773
2
votes
0
answers
61
views
Does absolute retract imply convex structure?
In the theory of selection, it is known that any compact absolute retract (AR) carries a convexity structure defined by E. Michael. It is also known that a convex structure
developed by Van de Vel ...
- 2,083
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
1
vote
1
answer
337
views
High-dimensional polytopes
I have two questions regarding polytopes in high dimensions, $\mathbb{R}^d$ where $d > 3$, that I could not find resources for on the web for. Suppose I have a polytope that is non-convex:
How can ...
- 43
0
votes
1
answer
428
views
The dimension of the normal cone of a face in a polytope
Let $P$ is a polytope in $\mathbb{R}^n$ if $F$ is one of its faces of dimension $d$ then the dimension of its normal cone $\mathcal{N}(F)$ is $n-d$.\
This seems to be intuitively obvious but I can't ...
23
votes
3
answers
3k
views
How many different numbers can be obtained as product of first $n$ natural numbers?
Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...
- 323
56
votes
1
answer
3k
views
Intersecting family of triangulations
Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
- 24.7k
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
6
votes
2
answers
371
views
Parallelotope fundamental domains of the n-torus
The group $\mathbb Z^n$ acts on the topological space $\mathbb R^n$ by translation: if $z = (z_1, \cdots, z_n) \in \mathbb Z^n$ and $x = (x_1, \cdots, x_n) \in \mathbb R^n$, then $z\cdot x := z+x$. ...
- 161
0
votes
1
answer
110
views
Detecting non-negativity of a single constraint by polyhedral constraints - $I$
We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\...
- 13.9k
13
votes
2
answers
3k
views
How many vertices/edges/faces at most for a convex polyhedron that tiles space?
I wonder if this problem has already been examined before:
Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have?
...
- 13.4k
12
votes
2
answers
510
views
Positivity of the coefficients of the Ehrhart polynomial of a cross-polytope
Question 35996 asks about the Ehrhart polynomial $i_d(n)$ of the
standard regular cross-polytope. It can be defined equivalently by
$$ \sum_{n\geq 0}i_d(n)x^n = \frac{(1+x)^d}{(1-x)^{d+1}}. $$
It ...
- 50.8k
16
votes
1
answer
587
views
Convex hull of all rank-$1$ $\{-1, 1\}$-matrices?
Consider the set $\mathbb{R}^{m \times n}$ of $m \times n$ matrices. I am particularly interested in properties of polytope $P$ defined as a convex hull of all $\{-1,1\}$ matrices of rank $1$, that is,...
- 213
17
votes
6
answers
2k
views
On the number of Archimedean solids
Does anyone know of any good resources for the proof of the number of Archimedean solids (also known as semiregular polyhedra)?
I have seen a couple of algebraic discussions but no true proof. Also, ...
- 273
6
votes
1
answer
698
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
1
answer
184
views
What are midway sections of simplices?
This is a (slightly modified) crosspost.
Subsequent edit - coordinates are changed to obtain simpler expressions; the existing answer is not affected.
There is a family of convex polytopes: $P_n$ is $...
- 18.4k
4
votes
2
answers
190
views
Existence of a fundamental domain for the convex hull of group action on a rational polytope
Let $P \subset \mathbb R^n$ be a compact rational polytope (the affine space spanned by $P$ may not be $\mathbb R^n$). Let $G \subset {\bf GL}(n,\mathbb Z)$ be an arithmetic group. Let $$C = {\rm Conv}...
- 3,472
1
vote
0
answers
65
views
Minimum bounding rectangle of symmetric convex bodies in the plane : is the ball the worst case
The minimal rectangle containing the euclidean ball in the plane is the standard cube $B_\infty = [-1;1]^2$. I would like to know if the euclidean ball is the worst symmetric convex body to be ...
- 245
3
votes
0
answers
130
views
Counting lattice polytopes by volume
For any $n \in \mathbb{N}$ and $B \in \mathbb{R}_{\geq 0}$, let $\mathcal{P}(n,B)$ be the set of $n$-dimensional convex polytopes $\Delta \subseteq \mathbb{R}^n$, taken up to integral, unimodular ...
- 1,116
2
votes
1
answer
106
views
Are zonotopes determined by their edge-graph?
General polytopes are not determined by their edge-graph (up to combinatorial equivalence). But I came accross the statement that zonotopes are determined in this way.
Question: Is this true? And ...
- 13.6k
16
votes
5
answers
1k
views
Name of a polytope
What is the name of the polytope $\Sigma\cap (-\Sigma)$ for $\Sigma$ a $d-$simplex with barycenter at the origin?
In dimension $2$, one gets a hexagon, in dimension $3$ an octahedron (given by the $6$...
- 17.9k
1
vote
0
answers
32
views
Adjacent vertices of a permutohedron which is the orbit of a point $x$ with repeated coordinates
Question: Let $x=(x_1, ..., x_n) \in \mathbb{R}^n$, and let $P$ be the convex hull of the points formed by permuting the coordinates of $x$. Given a vertex $y$ of $P$, what is a general rule for ...
- 637