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
2 votes
1 answer
95 views

A matrix that commutes with all symmetries of a vertex-transitive polytope

Let $P\subset\Bbb R^d$ be a vertex-transitive polytope aka. an orbit polytope. Can there be a matrix $T\in\mathrm{SO}(\Bbb R^d)$ that commutes with all symmetries in $\mathrm{Aut}(P)\subset\mathrm O(\...
M. Winter's user avatar
  • 12.5k
1 vote
0 answers
49 views

How does one translate from convex hull to a set of facets (inequalities)? [duplicate]

Suppose I have defined a convex set as the convex hull of a set of points. (I know that all these points are "extremal points" of the convex set.) I know want to translate this description of the ...
guest's user avatar
  • 11
5 votes
1 answer
446 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 $\...
Elle Najt's user avatar
  • 1,422
0 votes
1 answer
277 views

Overlap count of convex combination of points [closed]

Let $x_1, ..., x_n\in\mathbb{R}^d$. We know that a point $x$ in the convex hull $\text{conv}(x_1, ..., x_n)$ may be expressed as convex combinations $x=\sum_{i=1}^n r_ix_i=\sum_{i=1}^n s_ix_i$ with ...
Min Wu's user avatar
  • 461
4 votes
3 answers
597 views

An example of a "simple poset" which does not belong to a convex polytope

Are there examples of d-regular graphs (i.e. graphs where every node has exactly d adjacent nodes) which are not the 1-skeleton of a simple convex polytope? UPDATE: New version of the question: is ...
giulio bullsaver's user avatar
5 votes
1 answer
264 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 ...
M. Winter's user avatar
  • 12.5k
4 votes
2 answers
167 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 ...
M. Winter's user avatar
  • 12.5k
3 votes
1 answer
149 views

Are there any more polytopes whose 2-faces are identical 4-gons?

What are examples for convex polytope $P\subset \Bbb R^d,d\ge 3$ for which holds $P$ is 2-face transitive (that is, all 2-faces are equivalent under the symmetries of $P$), and all 2-faces of $P$ are ...
M. Winter's user avatar
  • 12.5k
7 votes
1 answer
482 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 ...
Joseph O'Rourke's user avatar
5 votes
1 answer
402 views

Iterated derivative and rectangular standard Young tableaux

We first make a few definitions, seemingly out of the blue (they are introduced/defined in this paper). Let $F^0_{a}(z) = (1-z)^{-1}$ and define recursively $$ F^{k+1}_{a}(z) = z^{a-1} \frac{d^a}{dz^...
Per Alexandersson's user avatar
6 votes
1 answer
624 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 ...
Daron's user avatar
  • 1,761
3 votes
0 answers
261 views

Guises of the refined Eulerian numbers, generated by tangent vectors (OEIS A145271)

The Eulerian numbers (OEIS A008292, not to be confused with the Euler numbers) pop up in numerous scenarios in combinatorics and advanced analysis, one as the components of the h-vectors of the ...
Tom Copeland's user avatar
  • 9,897
3 votes
1 answer
312 views

How can the same polytope have three different volumes? [closed]

I'm quite new to geometry and I came across the idea that the same convex polytope can have at least three different volumes. Consider the permutohedron, formed by the convex hull of the n! points ...
RMurphy's user avatar
  • 163
1 vote
0 answers
214 views

Gaussian mean width of normal random cones

Suppose $1 \leq n < m < \infty$ are integers. For $g \sim \mathcal N(0, I_n)$ define the gaussian mean width of a non-empty set $T \subseteq \mathbb R^n$ by $$ w(T) := \mathbb E \sup_{x \in T} \...
bashfuloctopus's user avatar
1 vote
0 answers
39 views

Partition complexity measure of the boolean cube?

Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the ...
Turbo's user avatar
  • 13.6k
8 votes
3 answers
369 views

Is there any edge- but not vertex-transitive polytope in $d\ge 4$ dimensions?

I consider convex polytopes $P\subset\Bbb R^d$. The polytope is called vertex- resp. edge-transitive, if any vertex resp. edge can be mapped to any other by a symmetry of the polytope. I am looking ...
M. Winter's user avatar
  • 12.5k
1 vote
0 answers
48 views

Realizing 0/1-polytopes with shortest possible edge lengths

Has there been something written about the following question? Question: Given a 0/1-polytope, what is the shortest edge lengths with which this polytope can be realized as a 0/1-polytope. The ...
M. Winter's user avatar
  • 12.5k
1 vote
1 answer
102 views

A source for $01$-polytopes

Can you recommend any books or survey articles on $01$-polytopes, thats is, polytopes with vertices in $\{0,1\}^n$? I am less interested in random $01$-polytopes, but more in the combinatorial ...
M. Winter's user avatar
  • 12.5k
2 votes
1 answer
85 views

The number of Hamiltonian circuits on a convex polytope embedded in $\mathbb{R}^N$

Recently I wondered whether there might be a natural topological complexity measure for convex polytopes embedded in $\mathbb{R}^N$. After some reflection it occurred to me that the number of distinct ...
Aidan Rocke's user avatar
  • 3,807
2 votes
1 answer
117 views

Polytopes and polyhedral cones in complex Euclidean space

Given $A \in \mathsf{M}_{m \times n}(\mathbb{R})$ and $b \in \mathbb{R}^m$, the polyhedron with respect to $A$ and $b$, denoted by $P(A,b)$, is defined by $$ \{ x \in \mathbb{R}^n \mid Ax \le b \}.$$ ...
Pietro Paparella's user avatar
2 votes
0 answers
84 views

Iterated polyhedron face twisting

Let $Q$ be a polygon in the plane. Modify $Q$ by rotating each edge about its midpoint by $180^\circ$. The result is $Q$ again: No change. This suggests exploring a similar operation in $\mathbb{R}^3$...
Joseph O'Rourke's user avatar
3 votes
1 answer
91 views

Regular triangulations of star-convex polyhedra with given boundary

Given an $n$-dimensional star-convex polyhedron $P\subset \mathbb{R}^n$ with simplicial facets, is it always possible to construct a regular triangulation $K$ of $P$ which does not subdivide the ...
user136604's user avatar
1 vote
0 answers
67 views

Is there a simple polyhedral characterization of these integral points?

Given $n\in\mathbb Z_{>0}$ consider the set of $n$-tuples $$(a_1,\dots,a_n)\in\mathbb Z_{\geq0}^n$$ on following simple conditions $0\leq a_i\leq 2^{2^n}-1$ If $a_i=b_{i,2^{n}-1}2^{2^{n}-1}+\dots+...
Turbo's user avatar
  • 13.6k
1 vote
1 answer
98 views

Estimating volume of a simple object

Volume computation is $\#P$ hard. Take the $[0,1]^n$ polytope. Slice it by an half space inequality with $poly(n)$ bit rational coefficients into two unequal halves. Volume of bigger section is $\...
Turbo's user avatar
  • 13.6k
6 votes
1 answer
308 views

Edges of the contact polytope of the Leech lattice

Let $P\subset\Bbb R^{24}$ be the contact polytope of the Leech lattice, that is, $P$ is the convex hull of the 196,560 shortest vectors of $\Lambda_{24}$. Question: What are the edges of $P$? Let'...
M. Winter's user avatar
  • 12.5k
1 vote
1 answer
111 views

Given $H_{N}=\{\vec{x} \in [-1,1]^N:\sum_{i=1}^N x_i = 0\}$, what is the smallest subset $S \subset H_{2N}$ such that $\mathrm{conv}(S)=H_{2N}$

Motivation: This is related to a different question I asked in April. It occurred to me while thinking about the sums of uniform random variables and it stuck in my mind because it's the special case ...
Aidan Rocke's user avatar
  • 3,807
6 votes
0 answers
232 views

Complexity of scissors congruence?

Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with ...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
110 views

Two Questions on Tetrahedra and Platonic Solids [closed]

As was known to the ancients, two congruent regular tetrahedra can be inscribed in a cube and likewise 5 congruent regular tetrahedra can be inscribed in a regular dodecahedron. Is the converse to ...
Fred's user avatar
  • 157
5 votes
1 answer
265 views

Sufficient criterion for a simplicial sphere to be polytopal

Are there any purely combinatorial criteria which allow you to deduce that a spherical simplicial complex is polytopal (i.e., there exists a simplicial polytope whose boundary is isomorphic to it)? ...
Hugh Thomas's user avatar
  • 6,075
1 vote
0 answers
87 views

Formula for exponential integral over a cone

While reading 'Computing the Volume, Counting Integral points, and Exponential Sums' by A. Barvinok (1993), I came across the following: "Moreover, let $K$ be the conic hull of linearly independent ...
Erik's user avatar
  • 81
11 votes
1 answer
219 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 ...
M. Winter's user avatar
  • 12.5k
2 votes
2 answers
272 views

A conjecture concerning symmetric convex sets [closed]

Question: Let's suppose that $S \subset \mathbb{R}^n$ is convex and symmetric so: \begin{equation} x \in S \iff -x \in S \tag{1} \end{equation} Now, if we define the radius of $S$ as $R$ such that: \...
Aidan Rocke's user avatar
  • 3,807
1 vote
0 answers
62 views

Projection of a polytope along 4 orthogonal axes

Consider the following problem: Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
Alina's user avatar
  • 11
6 votes
1 answer
366 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 ...
Jialong Deng's user avatar
  • 1,749
1 vote
0 answers
94 views

Family of polytopes whose measure respects multiplication?

Is there a family $\mathcal{P}$ of integral polytopes and a polytope product $\star$ such that for every $n\in\mathbb N_{>1}$ $\exists p\in\mathcal{P}:vol(p)=n$ and $\forall q\in\mathcal{P}\...
Turbo's user avatar
  • 13.6k
2 votes
0 answers
87 views

Integrality of integral polytope?

Given a convex polytope with integral vertices presented in half-space description is there a way to test in polynomial time or polynomial hierarchy if polytope has integral volume? Finding ...
Turbo's user avatar
  • 13.6k
2 votes
0 answers
41 views

Describing hull of vertex intersections of two convex bounded polytopes?

We have two convex bounded polytopes $P_1$ and $P_2$ where a. $P_2\subseteq P_1$ b. $\mathcal{V}(P_2)\cap\mathcal{V}(P_1)\neq\emptyset$. Is there a name for the polytope $P=\mbox{Conv}(\mathcal{V}(...
Turbo's user avatar
  • 13.6k
3 votes
1 answer
211 views

What importance does the Hirsch conjecture have to Simplex Complexity?

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$. After being open for decades, Francisco Santos has ...
VS.'s user avatar
  • 1,816
5 votes
3 answers
653 views

Alexandrov's generalization of Cauchy's rigidity theorem

Wikipedia states that A. D. Alexandrov generalized Cauchy's rigidity theorem for polyhedra to higher dimensions. The relevant statement in the article is not linked to any source. The sources at the ...
M. Winter's user avatar
  • 12.5k
1 vote
0 answers
104 views

John's ellipsoid of a polytope

Suppose that $X$ is $\mathbb R^n$ with some polyhedral norm, that is, the unit ball of $X$ is an $n$-dimensional polytope. Assume that the John ellipsoid of $X$ is an Euclidean ball that touches every ...
Jan_Ch.'s user avatar
  • 113
4 votes
1 answer
259 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 ...
VS.'s user avatar
  • 1,816
4 votes
1 answer
165 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 ...
guigux's user avatar
  • 607
2 votes
1 answer
344 views

Upper bound on number of vertices in intersection (and union) of simplices

Let $S_1, \dots, S_k \subset \mathbb{R}^n$ be a set of (non-regular) simplices. Let $m_i$ indicate the number of vertices of simplex $S_i$ (we do not assume it is equal to $n-1$). Is there a simple ...
Artemy's user avatar
  • 650
2 votes
1 answer
240 views

Does quantifier elimination help here?

Suppose we have a quantified linear program $$\exists z_1,\dots,z_{poly(n)}\in\mathbb R$$ $$\exists u_1,\dots,u_n\in\mathcal P\cap\mathbb R^m$$ $$\forall v_1,\dots,v_n\in\mathcal P\cap\mathbb R^m$$ $$...
VS.'s user avatar
  • 1,816
2 votes
0 answers
29 views

When do projection maps of polyhedra factor?

Given three polyhedra $P$, $Q$, and $R$ in dimensions $a$, $b$, and $c$ respectively, with $a\leq b\leq c$, with the additional condition that: $P=\pi_1(Q)=\pi_2(R)$, where $\pi_1$ and $\pi_2$ are ...
VS.'s user avatar
  • 1,816
3 votes
1 answer
149 views

A question about polytopes related to linear programming

Given linear functions $f_1({\bf x}),\dots,f_n({\bf x})$ on ${\bf R}^m$, let $K = \{(a_1,\dots,a_n) \in {\bf R}^n:$ the $n$ halfspaces $\{{\bf x}: f_i({\bf x}) \leq a_i\} $ have nonempty intersection$\...
James Propp's user avatar
  • 19.4k
3 votes
1 answer
286 views

How to find the vertices of the set $\{v_i\in \mathbb{R}:a_1\ge v_1\ge v_2\ge \cdots\ge v_n\ge 0,\ q_2\le \sum_{i=1}^n p_iv_i\le q_1\}$

I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, $q_2\le \sum_{i=1}^n p_iv_i\le q_1$, with $\{p_i\}_{i=1}^n,\ q_1,q_2$ positive reals, and only one bound for the coordinates: $v_1\...
Samrat Mukhopadhyay's user avatar
3 votes
1 answer
271 views

On decomposition of polytopes

Given $m$ number of convex polytopes each with $v$ vertices and described by $h$ hyperplane inequalities in $\mathbb R^t$ are there operations on these polytopes that combine then to give an $v^{\...
VS.'s user avatar
  • 1,816
2 votes
0 answers
251 views

Understanding the geometry of $H_{n}=\{\vec{x} \in [-N,N]^n:\sum_{i=1}^n x_i = 0\}$

I am not an expert in convex geometry but if we define $a_i \sim \mathcal{U}([-N,N])$ where $[-N,N] \subset \mathbb{R}$ and $S_n = \sum_{i=1}^n a_i$ I suspect that for arbitrary $N \in [1, \infty) $: ...
Aidan Rocke's user avatar
  • 3,807
1 vote
0 answers
120 views

Mixed integer formulation of union of polytopes?

Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
VS.'s user avatar
  • 1,816

1
4 5
6
7 8
19