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

Filter by
Sorted by
Tagged with
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 ...
ABIM's user avatar
  • 5,019
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 ...
hyyyyy's user avatar
  • 233
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 ...
Arshak Aivazian's user avatar
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 ...
dohmatob's user avatar
  • 6,716
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 ...
dohmatob's user avatar
  • 6,716
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-...
dohmatob's user avatar
  • 6,716
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 ...
Tom Copeland's user avatar
  • 9,937
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\}, $$ ...
RyanChan's user avatar
  • 550
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\}$....
M. Winter's user avatar
  • 12.5k
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 ...
Gericault's user avatar
  • 225
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{...
RyanChan's user avatar
  • 550
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 ...
Shijie Gu's user avatar
  • 1,936
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'...
Tom Copeland's user avatar
  • 9,937
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 ...
user73577's user avatar
  • 405
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 ...
asv's user avatar
  • 21.1k
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 ...
Luis Ferroni's user avatar
  • 1,879
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?
Daniel Sebald's user avatar
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}, ...
Daniel Turizo's user avatar
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 ...
Mathlover's user avatar
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 ...
Sam Hopkins's user avatar
  • 22.7k
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$...
DASON's user avatar
  • 118
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 ...
Guillaume Aubrun's user avatar
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 ...
lrnv's user avatar
  • 686
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?
Daniel Sebald's user avatar
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 ...
efs's user avatar
  • 3,099
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 ...
Daniel Turizo's user avatar
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$ ...
user73577's user avatar
  • 405
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 ...
maths123456's user avatar
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 ...
asv's user avatar
  • 21.1k
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 $...
Avi Steiner's user avatar
  • 3,031
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 ...
Daniel Sebald's user avatar
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." ...
Michael Hardy's user avatar
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 ...
GuyS's user avatar
  • 43
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 ...
FermaX's user avatar
  • 33
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 ...
Dasha Poliakova's user avatar
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 ...
CWC's user avatar
  • 359
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 ...
Riccardo Pengo's user avatar
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 $\...
IAnemaet's user avatar
  • 153
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 ...
Jose Capco's user avatar
  • 2,175
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 ...
Nick Matteo's user avatar
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 ...
Joseph O'Rourke's user avatar
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 ...
Dasha Poliakova's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Turbo's user avatar
  • 13.7k
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_{\...
Turbo's user avatar
  • 13.7k
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 $\...
Turbo's user avatar
  • 13.7k
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 ...
Dasha Poliakova's user avatar
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}...
Rybin Dmitry's user avatar
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/...
Dmytro Taranovsky's user avatar
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\...
Turbo's user avatar
  • 13.7k

1 2
3
4 5
19