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
4
votes
2
answers
415
views
Selecting vertices in a convex polygon
Given $n$ vertices of a convex polygon in $\mathbb{R}^2$, selecting two points that are furthest apart is done by finding the diameter in a convex polygon. But how can one select three vertices such ...
- 51
8
votes
1
answer
153
views
The polytope algebras generated by polytopes with rational vs arbitrary vertices
The polytope algebra was defined by P. McMullen in "The polytope algebra" Adv. Math. 78 (1989) as follows.
Let us denote by $\Pi'_\mathbb{R}$ the quotient of the free abelian group generated ...
- 21.8k
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
1
vote
0
answers
71
views
Diminishing of the $4_{21}$
One of the projections of the $4_{21}$ polytope (https://en.m.wikipedia.org/wiki/4_21_polytope) into four dimensions positions its vertices as those of two concentric 600-cells scaled by the golden ...
- 2,773
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." ...
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
3
votes
1
answer
171
views
Covering radius of a lattice from relevant vectors
Let $L$ be an $n-$dimensional lattice. The Voronoi region of $L$ is given by
$$
\mathcal{V}(L)=\big\{x\in\mathbb{R}^n~|~ \|x\|_2\leq \|x-v\|_2~\forall v\in L\setminus\{0\}\big\}.
$$
Considering the ...
- 33
3
votes
1
answer
105
views
What property of ranked poset ensures that it is determined by its vertex-facet incidences?
For a convex polytope, its face poset is combinatorially determined by vertex-facet incidences. Now suppose we have an arbitrary finite poset that is ranked, so I can still speak of vertices and ...
- 765
4
votes
1
answer
274
views
"Permutation matrix" but non-zero entries are replaced by $e^{ix}$
Birkhoff–von Neumann theorem states that a polytope formed by a set of doubly-stochastic matrices has extreme points that are permutation matrices.
I am wondering if there is a similar theorem for a ...
- 433
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
1
vote
0
answers
58
views
Generalisation of spanning tree in simplex
This is a question I asked on Stackexchange (https://math.stackexchange.com/q/4004734/400240) but I did not receive an answer (I think it was too hard). Per someone's suggestion I put it here.
Let $\...
- 153
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
2
votes
1
answer
64
views
Definition of "regular" in Stringham's "Regular figures in n-dimensional space"
I've been reading Irving Stringham's 1880 thesis, "Regular Figures in n-dimensional Space" (only 14 pages!), after it was mentioned by Coxeter in Regular Polytopes (§7.x).
I'm confused about ...
- 590
24
votes
1
answer
1k
views
Which unfoldings of the $d$-dimensional hypercube tile $(d{-}1)$-space?
A six year old question,
Which unfoldings of the hypercube tile $3$-space?, has just been answered by
Moritz Firsching:
All $261$ unfoldings tile space!
So now we know:
For $d=2$, the unfolding of ...
- 151k
3
votes
0
answers
111
views
"Slim" directed polytopes: any established name for them?
This is a "looking for context" question.
Let's say that a polytope is directed if its 1-skeleton is an oriented graph with no cycles, one source, one sink. (Edit: let us additionally assume ...
- 765
1
vote
0
answers
63
views
Counting $\bmod 2$ number of vertices of sparsely represented polyhedra
Given a polyhedron
$$Ax\geq b$$
is there an $NC^1$ or an $NC^2$ algorithm to count the number of vertices $\bmod2$?
Assume $A\in\{0,1\}^{m\times n}$ and $b\in\mathbb Z^{m}$ ($m=O(n)$) and assume rows ...
- 13.9k
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
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
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
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
3
votes
0
answers
154
views
Ehrhart-Macdonald reciprocity with multiplicities
Let $P$ be a convex lattice polytope in $\mathbb{R}^n$. The function $L(t, P) = |\mathbb{Z}^n \cap t\cdot P|$ is a polynomial, and we have an equality
$$L(-t, P) = (-1)^nL(t, P^{int}),$$
where $P^{int}...
- 645
0
votes
0
answers
98
views
Asymptotic optimal sphericity
How quickly does maximum sphericity of polyhedra with $n$ faces approach 1 as $n→∞$? I can show that sphericity $1 - \frac{5 \sqrt{3} π}{27n} - O(n^{-3/2})$ is possible. Is this, especially $O(n^{-3/...
- 7,545
1
vote
0
answers
122
views
Integrality of polyhedra
Given two polyhedra in $H$ representation $P_1:Ax\leq b$ and $P_2:Bx\leq c$ which are integral are bounded when is their intersection also integral?
Given two polyhedra in $H$ representation $P_1:Ax\...
- 13.9k
2
votes
0
answers
106
views
How to judge whether the following convex set contains a given point?
Let the set $\mathcal{S}=\left\{ \sum_{i=1}^n x_i\mathbf{h}_i：x_i\in[0,1] \text{ for all }i\right\}\subset\mathbb{R}^r$, i.e., a zonotope generated by $n$ column vector $\mathbf{h_1},\cdots,\mathbf{h}...
- 550
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
0
votes
0
answers
93
views
Number of vertices in a polyhedron
Consider polytopes
$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$
$$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$
$$B[z_{1},z_{2},z]'\leq c$$
having vertex count $v_1,v_2$ and $v$ respectively.
We ...
- 13.9k
4
votes
1
answer
290
views
Intrinsic definition of a cone in a normal fan
Let $P\subseteq \mathbb{R}^n$ be a full dimensional polytope. Let us assume that $P$ has a facet description with the following inequalities:
$$ \left<x,u_F\right> \geq -a_F$$
where $u_F\in \...
- 1,889
1
vote
0
answers
36
views
How to express a polytope by a matrix inequalty? [duplicate]
Consider a convex V-polytope generated by the origin and $n$ points $\mathbf{h}_1,\cdots,\mathbf{h}_n$ in $\mathbb{R}^r$. A Theorem in the area of convex geometry shows that each V-polytope is a H-...
- 550
2
votes
0
answers
138
views
Is the projective symmetry group of a polytope more general than its linear symmetry group?
Give a (convex) polytope $P\subset\Bbb R^d$ (the convex hull of finitely many points). Consider its linear and projective symmetry groups:
\begin{align}
\DeclareMathOperator{\Aut}{Aut}
\...
- 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
149
views
A combinatorial characterization of the central inversion of a polytope?
Given a convex full-dimensional polytope $P\subset\Bbb R^d$ (convex hull of finitely many points and not contained in any proper affine subspace) and a symmetry thereof (a linear map $\smash{T\in\...
- 13.6k
0
votes
4
answers
457
views
Confining a polytope to one side of an affine hyperplane
Judging whether one convex polytope is inside of another when both are expressed as a system of linear inequalities seems not to be an easy problem.
This answer on math.stackexchange.com claims the ...
- 2,239
4
votes
0
answers
130
views
"Baues poset" of shellings of simplicial polytope?
Let me start with some background I want to use as analogy.
Consider a (convex) polytope $P$ and its set of triangulations. Among all the triangulations, a well behaved subset are the regular ones: ...
- 24.2k
16
votes
1
answer
508
views
Can solutions to Thomson's problem have pentagons?
Thomson's problem asks for the minimum-energy configuration for $N$ electrons on a sphere (refs: https://en.wikipedia.org/wiki/Thomson_problem, https://sites.google.com/site/adilmmughal/...
- 1,203
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
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
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
7
votes
1
answer
313
views
Iterating projections to random halfspaces
Consider the following process:
Start with a set $S = \mathbb R^n$. Repeat $L$ times: choose a random orthonormal basis $u_1, \ldots, u_n$, and consider the cone $C = \{ \sum \alpha_i u_i : \alpha_i \...
- 233
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
2
votes
1
answer
119
views
Anchor sets for lattice polygons: Part I
Suppose $V=\{(x_1,y_1), (x_2,y_2),\dots,(x_v,y_v)\}$ is a vertex set of lattice points satisfying
$$0=x_1<x_2<\dots<x_v \qquad \text{and} \qquad y_1>y_2>\cdots>y_{v-1}>y_v=0.$$
...
- 43.2k
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
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
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
15
votes
2
answers
481
views
Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?
For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices
$$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\
\pi_{2,1} & \ddots & \...
- 24.2k
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
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
9
votes
2
answers
341
views
Are there centrally-symmetric self-dual polytopes in dimension $d> 4$?
A convex polytope $P\subset\Bbb R^d$ is centrally symmetric if $-P=P$. It is self-dual (or better, self-polar?) if its polar dual $P^\circ$ is congruent to $P$, that is, there is a map $X\in\mathrm O(\...
- 13.6k
0
votes
0
answers
54
views
Attached convex "hulls"
Let $\mathcal{P}$ a finite set of points of a Euclidean $\mathbb{E}^n$ and take the union $\mathrm{U}(\mathcal{P})$ of all closed half-spaces defined by $n$ elements of $\mathcal{P}$ that contain only ...
- 13.2k
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
8
votes
2
answers
213
views
Constructing a $0/1$ polytope from an abstract simplicial complex
Let us fix $\Delta$ a finite simplicial complex, and label the vertices of $\Delta$ as $\{1,2,\ldots,n\}$. For each $F\in \Delta$ let us consider the point in $\mathbb{R}^n$ given by:
$$e_F := \sum_{i\...
- 1,889