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
128
views
State-of-the-art article on "uniform 5-polytopes?"
I would like to read article(s) that provide the “state of the art” on the following open problem:
“Enumerate all convex uniform 5-polytopes.”
This problem is posted on the “Open Problem Garden” (http:...
- 155
31
votes
2
answers
2k
views
The logic of convex sets
Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so ...
- 33.8k
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
4
votes
1
answer
200
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 ...
- 5,215
2
votes
0
answers
93
views
An easy way to recognize the edges of an orbit polytope?
Given a finite (orthogonal) matrix group $\Gamma\subseteq\mathrm O(\Bbb R^d)$ and a point $x\in\Bbb R^d$. The corresponding orbit polytope is
$$\mathrm{Orb}(\Gamma,x):=\mathrm{conv}\{Tx\mid T\in \...
- 13.6k
1
vote
1
answer
409
views
Exact volume calculation of a polytope is NP hard under which restrictions?
Computing the exact volume of a polytope given in half space representation seems to be NP-hard. One paper I found proved it is hard for rational coefficients. (However, the paper itself was behind a ...
- 121
25
votes
2
answers
1k
views
Complete the following sequence: point, triangle, octahedron, . . . in a dg-category
Let $\mathcal C$ be a pre-triangulated dg-category (or a stable $\infty$-category, if you wish).
An object $X$ in $\mathcal C$ gives a "point":
$$X$$
A morphism $X\xrightarrow f Y$ in $\mathcal C$ ...
- 18.7k
4
votes
0
answers
229
views
How to find the dimension of the polar cone of a convex cone generated by some given vectors
Suppose we have access to a generating set $\{v_1, ..., v_k\}\subseteq\mathbb{R}^n$ of the convex cone $C=cone(v_1, ..., v_k)$, where $cone(\cdot)$ is the conical hull (i.e. nonnegative span) of ...
- 461
3
votes
0
answers
51
views
testing whether a polyhedral complex is convex
Definitions
A (polyhedral) cone in $\Bbb R^n$ is the solution set of a finite number of inequalities of the form $a_1x_1+\cdots+a_nx_n\geq 0$. Note that I don't require strict convexity, i.e. a cone $...
- 3,079
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
2
answers
411
views
Marked chain polytope, has this been studied?
Fix $n$ and consider the polytope given by the inequalities
$$x_i\leq x_j, \text{ and } 0 \leq x_i \leq a_i \text{ for all } 1\leq i<j \leq n,$$
where $a_i \leq a_i\leq \dots \leq a_n$ are fixed ...
- 15.8k
5
votes
2
answers
3k
views
How to break a concave polyhedron into a few convex polyhedron?
I would like to know is there a way to break a concave polyhedron into a few convex polyhedron?
- 51
3
votes
0
answers
135
views
Edges in the convex hull of the union of random polygons
Let $P$ and $Q$ be two convex polygons in $\mathbb{R}^2$. Given $a > 0$, denote by $aP$ its image under the dilation by $a$ centered around the origin (i.e. the polygon obtained by replacing each ...
- 2,216
2
votes
0
answers
54
views
Inverting "codimension matrix" for polytopes?
Let $P$ be an abstract polytope. Let's construct its square matrix $A$ as follows. Its lines and columns are labelled by all faces of $P$, of all dimensions. Put $A(F_1,F_2)=t^m$ if $F_1$ is a subface ...
- 765
6
votes
0
answers
381
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 ...
18
votes
3
answers
2k
views
Are the Platonic solids shadows of 4-polytopes?
Say that a 3D shadow of a 4-polytope is a parallel projection to 3-space, not necessarily orthogonal to that 3-space (that would make it an orthogonal projection).
I am wondering if each of the five ...
- 151k
5
votes
0
answers
139
views
How does a map from permutahedra to associahedra factor through multiplihedra?
Let $P_i$ denote permutahedra, $K_i$ associahedra and $J_i$ multiplihedra. In their famous paper on operadic diagonals, Saneblidze and Umble use a projection $p_i: P_i \to K_{i+1}$ which factors as $...
- 765
4
votes
4
answers
536
views
Vertex-transitive polytopes in any dimension with any number of vertices?
Given positive integers $d$ and $v$ with $v \geq d+1$, does there always exist a (convex) vertex-transitive $d$-polytope with $v$ vertices? It seems that the answer should be "obviously" true, but I ...
- 51
6
votes
5
answers
2k
views
How to prove that a set of facets are all the facets of a convex polytope.
Say that you know all the vertices of a polytope P, and a set of facet defining hyperplanes that you guess give all the facets of P. What are some good ways to try to prove that the guess is right?
A ...
- 614
1
vote
0
answers
323
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
9
votes
4
answers
1k
views
Positivity of Ehrhart polynomial coefficients
Are there any results stating that a given family of convex polytopes have Ehrhart polynomials with non-negative coefficients?
What methods are available for proving such a property for some family ...
- 15.8k
3
votes
0
answers
50
views
Modular counting of integral points under sparse non-negativity
Given a polyhedron
$$Ax\geq b$$
where every entry of $A,b$ are non-negative and $A\in\{0,1\}^{m\times n}$ and there are $O(1)$ (say $\leq8$) non-negative entries per row of $A$ is it possible to ...
- 13.9k
2
votes
2
answers
2k
views
Mathematical tools appropriate to analyse convex polyhedra
What mathematical tools (means: set of areas of mathematical knowledge) are appropriate to begin with to analyse (to enumerate face vectors associated with polyhedron, to calculate the combinatorial ...
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
1
vote
1
answer
184
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)$...
- 3,549
10
votes
3
answers
1k
views
Polytopes with few vertices.
Suppose I have a convex polytope in $\mathbb{R}^d$ which I know has few vertices (in the case which prompted this question, I seem to have a polytope in $\mathbb{R}^9$ which has sixteen vertices). Is ...
- 96.4k
1
vote
0
answers
43
views
Detecting non-negativity of a single constraint by polyhedral constraints - $II$
Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^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 $\mathbb Z_{\...
- 13.9k
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
3
votes
0
answers
87
views
Additional symmetries of the Traveling Salesman Polytope
Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
- 13.6k
6
votes
1
answer
133
views
How rich is the class of vertex- and edge-transitive polytopes?
There are only a few regular polytopes (five in 3D, six in 4D, three in any dimension above). In contrast, the class of uniform polytopes becomes very rich with higher dimensions.
The class of vertex-...
- 13.6k
6
votes
1
answer
453
views
When the image of a convex set in $\mathbb{R}^n$ is still a convex set?
Here is tricky problem I came across when writing a paper. But I can't figure it out, so I ask for help here.
Let $M$ be a $n$-dimensional smooth manifold which is also a complete geodesic space. We ...
- 1,799
7
votes
0
answers
152
views
Probability of landing inside the convex hull of previously sampled points
Let $\{X_i\}_{0\leq i\leq\infty}$ be i.i.d. random vectors in $\mathbb{R^d}$.
I would like to show that the probability of one point being in the convex hull of the others goes to one with the number ...
- 233
5
votes
1
answer
1k
views
Algorithms for projecting a point onto the convex hull spanned by a set of vectors
Given a set of vectors $V = \{ \mathbf{v}_1, \ldots, \mathbf{v}_n \} \subset \mathbb{R}^d$, I want to project a point $\mathbf{x}_0 \in \mathbb{R}^d$ onto the convex hull $\text{conv}(V)$ of the ...
- 283
25
votes
2
answers
692
views
Convex hull of total orders
Let $n$ be a positive integer and $\prec$ an arbitray total order on $\{1,\dots,n\}$. I associate to this order a vector $v$ with one coordinate for every pair $(i,j)$ s.t. $1\leq i\neq j \leq n$, by ...
- 4,484
0
votes
1
answer
97
views
If there are eigenvectors with largest components $i$ resp. $j$, then is there an eigenvector with two largest components $i$ and $j$?
Let $G=(V,E)$ be a connected (finite simple) graph with vertex set $V=\{1,...,n\}$ and let $\theta_2\in\Bbb R$ be the second-largest eigenvalue of its adjacency matrix. I wonder about the following ...
- 13.6k
3
votes
0
answers
58
views
Classifying/enumerating vertex-transitive simplicial polytopes
I'm interested in understanding the class of simplicial polytopes in $\mathbb R^n$ whose Euclidean isometry group $G$ acts transitively on the vertices. These are examples that I know of:
simplicial ...
- 191
4
votes
1
answer
193
views
Complexity of finding one vertex of a nonempty polytope
Let $P$ be a polytope given by some half-space description: $P=\{x\in\mathbb{R}^n: Ax\leq b\}$ for some $A\in\mathbb{R}^{m\times n}, b\in\mathbb{R}^m$, $m\geq n$. Assume that $x_0\in P$ for some given ...
- 617
10
votes
2
answers
691
views
Symmetries and faces of the associahedron
The dihedral group of order $2n+2$ acts on $K_n$, the ($n-2$)-dimensional associahedron. Are there any other symmetries? References?
Does the answer to 1 change if we restrict to just the 1-...
- 1,625
10
votes
3
answers
985
views
Approximate volume computation and lattice point enumeration - hardness
Both volume computation and lattice point enumeration of convex polyhedron are $\#P$ hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation.
...
- 13.9k
5
votes
0
answers
93
views
Which polytopes can be deformed while keeping their edge-lengths?
Let $P\subset\Bbb R^d$ be a convex polytope (a convex hull of finitely many points). Lets call it flexible, if it can be continuously deformed while
keeping its combinatorial type, and
keeping its ...
- 13.6k
4
votes
1
answer
265
views
Does Banach-Mazur distance between regular polygons admit any structure that lends to approximation or exact results in particular situations?
Banach-Mazur distance between $P_5$ and $P_3$ is $d(P_5,P_3)=1+\frac{\sqrt5}2$ where $P_n$ is regular polygon in $n$ sides. Do closed form or approximate results exist (at least at special infinitely ...
- 1,826
10
votes
1
answer
483
views
Odds on rolling a rhombicosidodecahedron
This is more of a curiosity to me, but I'm sure I don't have the mathematical skills to answer it. That said... I took a look at several other posts with questions that relate to this one, but I ...
- 103
2
votes
2
answers
196
views
Estimates on the number of vertices of reflexive polytopes
Suppose $M \cong \mathbb{Z}^n$ is a rank $n$ lattice, with dual lattice $N$. Suppose $\Delta$ is a full dimensional lattice polytope (i.e. convex hull of finite lattice points) in $M$. Then $\Delta$ ...
- 3,472
3
votes
1
answer
111
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 ...
- 13.6k
45
votes
1
answer
3k
views
two tetrahedra in $\mathbb R^4$
It is relatively easy to show (see below) that if we have two equilateral triangles of side 1 in $\mathbb R^3$,
such that their union has diameter $1,$ then they must share a vertex.
I wonder whether ...
- 1,359
1
vote
0
answers
87
views
refining a coherent triangulation
I am relatively new to this topic, so this question may be easy/naive to some experts. Here goes..
I have a finite set of points $S\subset\mathbb R^2$ (you may increase the dimension of the ambient ...
- 2,275
19
votes
2
answers
1k
views
About a Delzant polytope. (In particular dodecahedron)
Hi. I have a question.
Definition. Delzant polytope $P$ is a rational convex simple polytope with the smooth condition. Here, "smooth" means that for each vertex $v$, the $n$ edges containing $v$ ...
- 1,037
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-...
11
votes
1
answer
228
views
Geometric realization of combinatorial self-duality in polytopes
Let's say I have a combinatorially self-dual polytope $P\subseteq\Bbb R^d$, i.e., its face lattice is isomorphic to its dual (you reverse the direction of the lattice order).
Question: Is it always ...
- 13.6k
28
votes
1
answer
1k
views
Are Minkowski sums of upward closed "convex" sets in $\mathbb{N}^k$ still "convex"? (WAS: Comparing mana costs in Magic: The Gathering)
This was originally a question about comparing mana costs in Magic: The Gathering, but it's turned into a question about Minkowski sums of upward-closed convex sets in $\mathbb{N}^k$. The original ...
- 2,585