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

313 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
32 votes
0 answers
2k views

A Combinatorial Abstraction for The "Polynomial Hirsch Conjecture"

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ . Suppose that (*) For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
Gil Kalai's user avatar
  • 24.2k
29 votes
0 answers
3k views

Why do polytopes pop up in Lagrange inversion?

I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
19 votes
0 answers
551 views

"Japanese Theorem" on cyclic polygons: Higher-dimensional generalizations?

A beautiful theorem known as the Japanese Theorem (Wikipedia, MathWorld) says that, no matter how one triangulates a cyclic (inscribed in a circle) polygon, the sum of the radii of the incircles is ...
Joseph O'Rourke's user avatar
17 votes
0 answers
360 views

Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?

Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation it stays a convex polytope, it stays a combinatorial dodecahedron (i.e. its ...
M. Winter's user avatar
  • 12.5k
16 votes
1 answer
705 views

Inequalities for marginals of distribution on hyperplane

Let $H = \{ (a,b,c) \in \mathbb{Z}_{\geq 0}^3 : a+b+c=n \}$. If we have a probability distribution on $H$, we can take its marginals onto the $a$, $b$ and $c$ variables and obtain three probability ...
David E Speyer's user avatar
16 votes
0 answers
288 views

Realization spaces of 3-dimensional polytopes with fixed face areas

It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible. A proof of this theorem can be found for instance in ...
Misha's user avatar
  • 31k
14 votes
0 answers
201 views

Have there been further developments on this scheme for polytope approximations to the unit ball of $\ell_p^n$?

A long time ago I happened to look at, and save (on a floppy disk!) for future reading, a copy of the following article: W. T. Gowers, Polytope approximations of the unit ball of $l^n_p$. In Convex ...
Yemon Choi's user avatar
  • 25.5k
14 votes
0 answers
253 views

Is combinatorial automorphism of symmetric convex polytope always antipodal?

The question is formulated in the title. More precisely, if $P$ is an origin-symmetric convex polytope in $\mathbb{R}^d$, and $f$ is a bijective transform of the set of the vertices of $P$, which ...
Fedor Petrov's user avatar
14 votes
0 answers
258 views

Polytopes with few vertices and few facets

I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...
Arnau's user avatar
  • 278
14 votes
0 answers
477 views

Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?

After reading these very interesting questions, I came up with another one: Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
Piotr Shatalin's user avatar
13 votes
0 answers
251 views

Does there always exist a self dual polytope that contains a given polytope contained in its dual?

Suppose a polytope $P$ is contained in its dual polytope $\tilde{P}$. Does there always exist a polytope $Q$ that contains $P$ and is self dual $Q=\tilde{Q}$? Is there any bound on the minimal number ...
Huangjun Zhu's user avatar
13 votes
0 answers
1k views

Constructive aspects of Caratheodory's theorem in convex analysis

Let me paraphrase Caratheodory's theorem in a probabilistic setup: Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
gondolier's user avatar
  • 1,829
12 votes
0 answers
530 views

Reciprocity (Ehrhart-style) for real polytopes?

Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices? In other words, given any ...
11 votes
0 answers
294 views

How many ways to flatten a Tesseract onto a table?

A cube can be cut and flattened out onto a table in a way that the faces stay connected and none of them overlap. There are $384$ ways to make the cuts and $11$ distinct meshes emerge (see here). And ...
ryu576's user avatar
  • 171
11 votes
0 answers
337 views

Is my open set a ball?

Let $P$ be a polytope of dimension $n$, and let $\mathcal{C}$ be a polyhedral subdivision of $P$. That means that $\mathcal{C}$ is a finite collection of polytopes whose union is $P$, such that the ...
Nicholas Proudfoot's user avatar
11 votes
0 answers
344 views

Right-angled polytopes

%This question is motivated by the little discussion here at the bottom. The following thing are known about hyperbolic right-angled polytopes: Compact hyperbolic right-angled polytopes do not exist ...
SashaKolpakov's user avatar
11 votes
0 answers
364 views

Lower Bound on the Volume of Certain Polytopes

Given a partition $\rho\in\mathcal{P}(n)$ with $k$ blocks $$ \rho=\{B_1,B_2,\ldots,B_{k}\} $$ we can define the set of equations $$ E_{i}:\sum_{j \in B_{i}}{x_{j-1}}=\sum_{j \in B_{i}}{x_j}\quad\text{...
ght's user avatar
  • 3,616
10 votes
0 answers
329 views

Bi-spherical polyhedra

Bicentric polygons have been studied: a polygon all of whose vertices lie on its circumcirle, and whose incircle is tangent to every edge:   I have not been able to find a comparable literature ...
Joseph O'Rourke's user avatar
9 votes
0 answers
203 views

Positivity of coefficients of Ehrhart polynomial of n-Tetrahedron

A set of positive integers $d_1, \dots, d_n$ describe two n-dimensional closed lattice tetrahedron: $$ T = \left\{ (x_1, \dots, x_n) \in \mathbb{R}^n: \sum_{i=1}^n \frac{x_i}{d_i} \leq 1 \textrm{ and ...
Jiro's user avatar
  • 909
9 votes
0 answers
177 views

Is every planar point set the projection of vertices of a neighborly 4-polytope?

More exactly, written in coordinates, I'm curious to know if for every point set $(x_i,y_i)$ there are $(x_i,y_i,z_i,w_i)$ that are vertices of a neighborly polytope. This problem comes from a simple ...
Peter Wu's user avatar
  • 261
9 votes
0 answers
355 views

An affine invariant of convex bodies

The following invariants of "pointed" convex bodies (i.e., pairs consisting of a convex body and a distinguished point in its interior) roughly measure how many of its linear images fit between the ...
alvarezpaiva's user avatar
  • 13.2k
9 votes
0 answers
736 views

Counting Lattice Points in Real Polytopes

Suppose one did have an exact formula for the number of $\mathbb{Z}^n$-lattice points intersecting an arbitrary dilate of a (not necessarily rational) finite, closed and convex $n$-polytope. As a ...
8 votes
0 answers
270 views

Integral representations of finite groups and lattice point geometry

See the edit at the bottom (April 2021) This contains both a reference request, and a specific problem. Let $K$ be a finite group, and let $\theta: K \to {\rm GL}(d,{\bf Z})$ be a (faithful) group ...
David Handelman's user avatar
8 votes
0 answers
194 views

intriguing Polytope

Define $E_{i,j} \in \mathbb{R}^{n \times n}$ to be the canonical basis (that is all elements set to zero except the entry $i,j$ ) let the bloc matrix $M \in \mathbb{R}^{n^2 \times n^2}$ defined by : ...
Rémy Martin's user avatar
8 votes
0 answers
1k views

Maximum volume cross-section of a hypercube

This is surely well known, but: Q1. What is the $(d{-}1)$-dimensional polytope that realizes the maximum volume cross-section of a unit hypercube by a $(d{-}1)$-dimensional hyperplane? ...
Joseph O'Rourke's user avatar
8 votes
0 answers
178 views

Can the GUE be thought of as a uniform point in a high-dimensional polytope

I have thought about this question for a long time and could only find partial answers. The Gaussian Unitary Ensemble (or GUE) is the eigenvalues of a random Hermitian matrix with complex Gaussian ...
john mangual's user avatar
  • 22.6k
8 votes
0 answers
139 views

What does this number tell me about a convex lattice polygon?

EDIT: I realized I'd tricked myself by working with a too special case of $f$, the question is now updated (boundary lattice points replaced vertices). Suppose I have a convex lattice polygon $P$, ...
Ketil Tveiten's user avatar
8 votes
0 answers
144 views

How many facets can $\{\|D^T x\|_1\leq 1\}$ have?

$\newcommand{\RR}{\mathbb{R}}$Consider $x\in\RR^n$ and $D\in \RR^{n\times p}$ with $p\geq n$ and full rank. My question is: How many facets can the polytope $ \{x\in\RR^n\ :\ \|D^T x\|_1\leq 1\}$ ...
Dirk's user avatar
  • 12.3k
8 votes
0 answers
812 views

Geometry of the metric cone

Let us say that two metrics $d$ and $d_0$ on a set $X$ are related if there exist positive constants $0 < \alpha \leq \beta$ such that $$ \alpha \,\left(d_0(x,y) + d_0(y,z) - d_0(x,z)\right) \leq ...
alvarezpaiva's user avatar
  • 13.2k
8 votes
0 answers
5k views

Convex hulls of compact sets

Let $A$ be a compact set in a separable Hilbert space $H$, and let $\bar A$ denote its convex hull. Is $\bar A$ compact?
Tom LaGatta's user avatar
  • 8,362
7 votes
0 answers
158 views

Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets

We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
Penelope Benenati's user avatar
7 votes
0 answers
210 views

Tiling space with supertile of hypercube unfoldings

Two students in my class asked and answered what might be a novel question. It is well known that the cube has exactly $11$ edge-unfoldings (or "nets"), as shown below:         (Image from ...
Joseph O'Rourke's user avatar
7 votes
0 answers
136 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 ...
Maxim's user avatar
  • 233
7 votes
0 answers
358 views

A question about a blue fan and a red fan and their common refinement

Is the following conjecture true? Conjecture: Let $M_1$ be a red map and let $M_2$ be a blue map drawn in general position on $S^n$, and let $M$ be their common refinement. There is a vertex $w$ of $...
Gil Kalai's user avatar
  • 24.2k
7 votes
0 answers
634 views

When should a moment polytope have "smooth" faces?

A codimension $d$ face of a polytope is called rationally smooth if it lies on only $d$ facets, because this is exactly the condition for the corresponding toric variety to have only orbifold ...
Allen Knutson's user avatar
6 votes
0 answers
185 views

Zero-one pairings between sets of vectors

Let $A\subseteq V$ and $B\subseteq V^\star$ be spanning sets in a finite-dimensional real vector space $V$ and its dual $V^\star$. Suppose that $$ \langle b,a\rangle\in\lbrace0,1\rbrace $$ for all $a\...
Semen Podkorytov's user avatar
6 votes
0 answers
70 views

Roundest polyhedra: how well can we bound the edge count of their faces?

By "roundest" I mean having the lowest surface area for the highest volume, given a fixed number of faces $n$. There've been a few questions about them on here (including from me), but I'm ...
Robin Saunders's user avatar
6 votes
0 answers
313 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 ...
Guillermo Pineda-Villavicencio's user avatar
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
6 votes
0 answers
92 views

Tiling with Horn's polytopes

Let $n\ge2$ be an integer. Consider the hyperplane $H_n$ of ${\mathbb R}^n$ defined by the equation $x_1+\cdots+x_n=0$ and then the sector $P_n\subset H_n$ defined by the inequalities $x_1\le\cdots\le ...
Denis Serre's user avatar
  • 51.5k
6 votes
0 answers
188 views

Cut locus on a hypercube

Inspired by the question, "Shortest path connecting two opposite points on a cube": Q. What does the cut locus with respect to one corner of a hypercube in $\mathbb{R}^d$ look like? "The cut ...
Joseph O'Rourke's user avatar
6 votes
0 answers
113 views

Rational $d$-simplices

Define a rational $d$-simplex as a simplex in $\mathbb{R}^d$ such that the measure of all its $k$-dimensional faces, $k \ge 1$, is rational. So a rational triangle has rational edge lengths and ...
Joseph O'Rourke's user avatar
6 votes
0 answers
112 views

Convex hull of the orbit of a matrix under permutations

Let $P$ be a generic permutation matrix on $\mathbb{R}^n$. For any vector $x \in \mathbb{R}^n$, the convex hull of the set $\{ Px : \; \text{$P$ is a permutation matrix}\}$ is the set of vectors ...
passerby51's user avatar
  • 1,639
6 votes
0 answers
149 views

Measure-minimizing simplex with fixed inradius

Let $\Delta^n$ be an $n$-simplex in $\mathbb{R}^n$. Let $V$ be the volume and $r$ the inradius (radius of the inscribed sphere) of $\Delta^n$. There is a well-known result that $$ V \geq \frac{n^{n/2}(...
user108's user avatar
  • 93
6 votes
0 answers
181 views

Looking for the correct version of a wrong statement from Barvinok's book on convex polyhedra

The book I'm concerned with is "Integer Points in Polyhedra" by A. Barvinok, which, I must say, is turning out to be highly fascinating. A real finite-dimensional vector space $V$ defines the ...
Igor Makhlin's user avatar
  • 3,493
6 votes
0 answers
252 views

Sampling from a Convex Body with Many Extremal Points

Let $p_{1}, \ldots, p_{N}$ be a collection of points in $\mathbb{R}^{n}$. I would like to sample uniformly from the convex hull of these $N$ points in an `efficienct' way. In my setting, I have $n$ ...
qtrs's user avatar
  • 81
6 votes
0 answers
482 views

Minimum solid angle and aspect ratio of an $n$-simplex

In computational geometry and other fields, it is of interest to have degeneracy measures for shapes of simplices, which quantitatively seperate the regular simplex from degenerate simplices. In two ...
shuhalo's user avatar
  • 4,736
6 votes
1 answer
245 views

Triangulations of convex surfaces

Let $M$ be a smooth closed positively curved surface in Euclidean 3-space, $T$ be a geodesic triangulation of $M$, and $E$ be the edge graph of the convex hull of vertices of $T$. It is easy to see ...
Mohammad Ghomi's user avatar
5 votes
0 answers
149 views

Maximal number of vertices of the intersection of a flat and a hypercube

Consider the intersection of an $n$-dimensional hybercube and an $m$-dimensional flat (affine subspace) which contains the diagonal of the hypercube. This is a convex polytope. What is the maximal ...
Vanessa's user avatar
  • 1,368
5 votes
0 answers
88 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 ...
M. Winter's user avatar
  • 12.5k

1
2 3 4 5
7