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
918
questions
0
votes
0
answers
94
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 ...
6
votes
1
answer
226
views
Realizing spherical complexes as convex polytope
A spherical polytope is the intersection of some closed hemispheres which is non-empty and does not contain a pair of antipodal points. A spherical complex is a tiling of the whole (d−1)-dimensional ...
2
votes
0
answers
203
views
Do the polyhedral homologies of a polyhedron coincide with the polyhedral homologies of its subdivision?
Definition. A convex polytope is a compact finite intersection of hyperplanes in $\mathbb{R}^n$
Definition. The polycomplex is the following data set:
a set of convex polytopes, closed under ...
1
vote
1
answer
97
views
On the Lipschitz continuity of the unit-normal vector field of a polytope
Let $\mu$ be a probability measure on $\mathbb R^n$ and let $P$ be a compact polytope in $\mathbb R^n$. For any $x \in \mathbb R^n \setminus P$, let $p(x) \in P$ be (unique!) point in $P$ which is ...
2
votes
1
answer
111
views
Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points
Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$.
Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that
$$
\theta ...
2
votes
1
answer
121
views
Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$
Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
9
votes
1
answer
791
views
Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory
In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
1
vote
1
answer
89
views
How to compute external angles of a hypersimplex?
Recently, I concern with the volume of the outer parallel body of a hypersimplex that is defined as follows
$$
\mathcal{H}_s(n,k)=\left\{ (x_1,\cdots,x_n):\sum_{i=1}^n x_i=k,x_i\in[0,1] \right\},
$$
...
10
votes
3
answers
483
views
Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increases in length, can the circumradius still get larger?
Let $P\subset \Bbb R^n$ be an inscribed convex polytope, that is, all its vertices are on a common sphere of radius $r$.
Let $G$ be the edge-graph of $P$. For convenience, assume $V(G)=\{1,\dotsc,s\}$....
1
vote
0
answers
58
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 ...
4
votes
1
answer
169
views
How to solve this minimax matrix optimization problem?
Recently, I want to know how well can a $\ell_1$ ball be approximated by the image of a $\ell_2$ ball under a linear transform. I formulate this problem as the following optimization problem.
\begin{...
2
votes
0
answers
59
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 ...
1
vote
0
answers
363
views
Combinatorial proof of a matrix equation
I'm looking for combinatorial proofs (using, e.g., trees) of the following particular matrix equation $(I)$ and also combinatoric operational analogs of its solution via matrix inversion and/or Cramer'...
4
votes
1
answer
69
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 ...
3
votes
0
answers
167
views
Polytope algebra and toric vareties
Let $\Pi$ denote the McMullen polytope algebra (over the field of rationals $\mathbb{Q}$) generated by convex polytopes with rational vertices in $\mathbb{R}^n$.
For a simple polytope $P$ let us ...
3
votes
1
answer
239
views
Unimodality of $f$-vectors of $0/1$-polytopes
It is known that the face vectors (aka $f$-vectors) of general polytopes need not be unimodal. This even fails for simple or simplicial polytopes, as was shown first by Björner.
My question is if ...
0
votes
0
answers
91
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?
0
votes
1
answer
154
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}, ...
0
votes
1
answer
343
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 ...
2
votes
1
answer
128
views
Discrete random walk on polytope via involutions
Let $P$ be a convex polytope (or more generally convex body, I suppose) in $V=\mathbb{R}^n$. For each $v\in \mathbb{P}V$, we define an involution $\tau_v\colon P\to P$ by setting $\tau_v(p)$ to be the ...
4
votes
1
answer
180
views
What is the convex cone generated by the pair of rank 1 matrix and its eigenvector?
I'd like to know what is the convex cone generated by $\left\{ (h h^T, h) : h \in \Bbb R^{d\times1} \right\}$. It is known that $$\mathrm{cone} \left\{h h^T : h \in \Bbb R^{d \times1} \right\} = S_+^d$...
24
votes
1
answer
591
views
Polytope where each vertex belongs to all but two facets
Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a ...
1
vote
0
answers
76
views
Weird transportation polytope
I'm looking to compute extremal points of a weird polytope. This polytope contains all matrices with positive entries $A \in \mathcal M_{n,m}\left(\mathbb R_+\right)$ such that:
every row sum except ...
1
vote
1
answer
101
views
Graph diameter of the omnitruncated $E_8$ polytope
What is the graph diameter of the 1-skeleton of the omnitruncate of the $E_8$ family of uniform 8-polytopes?
3
votes
1
answer
342
views
Request for an article by Jim Lawrence
Jim Lawrence has a very important paper on the topic of valuations on polyhedra called "Rational-function-valued valuations on polyhedra", published in the DIMACS volume Discrete and ...
0
votes
0
answers
145
views
Minimum circumscribed ellipsoid of $\mathcal H$-polytope
Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows
$$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$
I ...
1
vote
0
answers
47
views
When is a PL function linear?
We have a simplicial decomposition of a $n$-dimensional disk $D_n$ an a PL function $\mu$ on the decomposition. For each set of vertices $v_1,\dots,v_n,v_{n+1}$, so that both $v_1,\dots,v_{n-1},v_n$ ...
4
votes
2
answers
391
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 ...
8
votes
1
answer
145
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 ...
3
votes
0
answers
49
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 $...
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 ...
1
vote
1
answer
128
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
268
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 ...
3
votes
1
answer
133
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 ...
2
votes
1
answer
98
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 ...
4
votes
1
answer
257
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 ...
3
votes
0
answers
125
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
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 $\...
1
vote
0
answers
76
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
votes
1
answer
53
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 ...
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 ...
3
votes
0
answers
110
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 ...
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 ...
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 ...
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_{\...
0
votes
1
answer
108
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 $\...
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 ...
3
votes
0
answers
140
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}...
0
votes
0
answers
94
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/...
1
vote
0
answers
118
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\...