# 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

922
questions

0
votes

0
answers

72
views

### Software for computing polytopes

As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...

0
votes

0
answers

57
views

### Probability of being inside a convex n-dimensional polytop

I am currently conducting some post-grad research about wireless transmissions with uncertain transmission delays.
As part of the research, each individual transmission is modelled using a probability ...

0
votes

0
answers

38
views

### Polyhedra volume, faces and edges from vertices

Given a set of vertices in 3D corresponding to a convex polyhedron, what is the most efficient way to find its volume, faces, and edges?
I've found some techniques using convex hulls. But I think I ...

10
votes

1
answer

136
views

### Is the face lattice of the cube a polytope graph?

The face lattice of a
convex polytope $P\subset\Bbb R^d$ is the partially ordered set whose elements are the faces of $P$ ordered by inclusion. We can turn it into a graph by considering its Hasse ...

2
votes

1
answer

196
views

### The realization space of non-convex polyhedra - What is known?

The space $\mathfrak R_{\mathrm c}(P)$ of convex realizations of a (3-dimensional, spherical) polyhedron $P$ is known to be well-behaved: it is a contractible manifold of dimension $\#\text{edges}+6$ (...

1
vote

1
answer

94
views

### Alexandrov's uniqueness theorem in Minkowski spacetime

Suppose $P$ is a convex polyhedron in $\mathbb{R}^{2,1}$.
Each face of $P$ comes with induced metric tensor,
if the face is space-like, then it is euclidean metric;
every time-like face is isometric ...

0
votes

1
answer

117
views

### Centroid of Minkowski sum

Let $A$ and $B$ be two compact convex subsets of $\mathbb{R}^n, n\geq 2$. Assume $x_A$ and $x_B$ are their respective centroid. If we form the Minkowski sum $C=A+B = \{x+y\mid x\in A, y\in B\}$, what ...

4
votes

0
answers

39
views

### Implementation of Friedman's algorithm of reconstructing simple polytopes

In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...

0
votes

1
answer

97
views

### Convex sets via fixed point equations

I have an equation of the general form
$$ X = S \cup T X $$
where $S \subset \mathbb R^n$ is a convex polytope (given by its bounding hyperplanes), $T\colon \mathbb R^n \to \mathbb R^n$ is a linear ...

1
vote

0
answers

40
views

### Polyhedra inscribed in a sphere with mutually non-congruent, equal area faces

Two constrained versions of the main question given in this post: Polyhedrons with mutually non-congruent faces, all of equal area. An earlier post that could be related: Cutting a spherical surface ...

1
vote

0
answers

108
views

### Homeomorphism between interiors of simplex and permutohedron

The $n$-dimensional permutohedron $P_n$ is a polytope whose facets (i.e.\ codimension $1$ faces) are in 1-to-1 correspondence with all faces (of codimension${}\geq 1$) of the $n$-simplex $\Delta_n$, ...

11
votes

0
answers

321
views

### Is a convex polyhedron determined by its edge lengths and angular defects?

Let's consider 3-dimensional convex polyhedra $P\subset\Bbb R^3$.
The angular defect at a vertex $v$ is $2\pi$ minus the sum of the interior angles of the incident faces at $v$.
Question:
Is a ...

0
votes

0
answers

66
views

### Using Ehrhart polynomials to count primes?

As indicated below, one could use the Ehrhart polynomials of the simplex in number theory.
Here are the questions without context first:
Questions:
The sum $$\sum_{k=0}^t (-1)^k ( \operatorname{...

7
votes

3
answers

638
views

### A continuous version of Carathéodory's convex hull theorem

A well-known theorem of Caratheodory states that any point in the convex hull of a set $X\subset R^n$ lies in the convex hull of at most $n+1$ points of $X$. I am wondering about a version of this ...

3
votes

0
answers

95
views

### Sampling uniformly from the convex cone

Let $n$ vectors of dimension $d$ (e.g., $n = 100$, $d = 10000$), each with infinity norm of $1$, be given. The conic combination of those $n$ vectors generates a convex cone.
How to uniformly sample ...

2
votes

0
answers

60
views

### Eulerian polynomial from Bruhat interval - h* of something?

Let $\sigma \in S_n$ be a fixed permutation.
Consider the polynomial
$$
P_{\sigma}(t) = \sum_{\substack{\pi \in S_n \\ \pi \leq \sigma}} t^{\textrm{des}(\pi)}
$$
where $\leq$ denotes Bruhat order, and ...

6
votes

0
answers

198
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\...

0
votes

1
answer

168
views

### Density of the set of convex polygons in the Banach-Mazur distance

Is the set of convex polygons dense in the set of convex domains in $\mathbb{R}^2$, for the Banach-Mazur distance?
Any insight for a negative or positive answer is very much welcome!

3
votes

0
answers

96
views

### Does there exist a finite-volume hyperbolic Coxeter polytope with these properties?

I searched for a finite-volume, hyperbolic Coxeter polytope of dimension $n \geq 4$ with the following properties $a$ and $b$.
$a$) It has exactly one ideal vertex;
$b$) if a bounded facet and an ...

3
votes

0
answers

52
views

### Volume of all Voronoi cells in n-dimensional bounded space

How can one find the volume of all Voronoi cells (bounded and unbounded) in an $n$-dimensional bounded space? For instance, consider an $N$-dimensional space (hypercube) with bounds on each dimension ...

0
votes

0
answers

59
views

### existence of moment maps for non-nef toric varieties

The noncompact toric variety $X_1 = \operatorname{Tot} \mathcal{O}(-1) + \mathcal{O}(-1) \to \mathbb{CP}^1$, the total space of the sum of two line bundles over the complex line, is defined as the ...

3
votes

0
answers

135
views

### How to sample uniformly over a polytope knowing its vertex presentation?

Say that a convex polytope $P$ is presented as $P = \mathrm{Conv}(v_1, \dots , v_m)$.
I would like to sample over $P$, without generating the facet presentation of the polytope.
How can I do that?
I ...

2
votes

1
answer

154
views

### Conic hull of a rectangle

I have a simple question that appeared in research: For a rectangle $S :=[a_1,b_1] \times[a_2,b_2] \times \dots \times [a_n,b_n] \subset \mathbb{R}^n$. Let $p_0 = (a_1,a_2,\dots,a_n)$, and define $p_i ...

4
votes

1
answer

174
views

### Denominators of rational polytopes in terms of hyperplane coefficients

Let $\mathcal{P}$ be a convex polytope in $\mathbb{R}^n$ given in the form $\mathcal{P} = \{ x \in \mathbb{R}^n\colon A x\leq b \}$. Suppose that the entries of $A$ and $b$ are integers. Then it is ...

3
votes

0
answers

121
views

### Does this construct Platonic solids?

Consider $\mathrm{O}(3)\curvearrowright\mathbb{R}^3$. Let $\Gamma\subseteq\mathrm{O}(3)$ be a finite group. Let $x\in \mathbb{R}^3\setminus\{0\}$ be a point such that $\mathrm{Stab}_\Gamma(x)$ has ...

2
votes

0
answers

47
views

### Estimating the Hausdorff distance of parallel facets of convex polytopes

Background
Let $\mathcal{K}_P^n$ denote the class of open, convex, $n$-dimensional polytopes in $\mathbb{R}^n$ containing the origin. For each $K\in \mathcal{K}_P^n$, its gauge function $f_*:\mathbb{R}...

4
votes

1
answer

283
views

### Does Kalai's $3^d$ conjecture hold for simplicial spheres?

Kalai's $3^d$ conjecture asserts that every centrally symmetric $d$-polytope has at least $3^d$ non-empty faces. This is open in general, but has been proven for simplicial polytopes.
Question: Does ...

2
votes

1
answer

152
views

### Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?

According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard.
However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...

3
votes

1
answer

37
views

### A converse question about the polyhedrality under linear mapping

It is quite well known that for any polyhedral set $K$ and any linear mapping $A$, the set $AK$ is polyhedral and hence closed. I am more curious about the converse problem, namely:
Suppose $K$ is a ...

0
votes

0
answers

90
views

### Which polytopes can be folded to an edge?

While playing with bar-and-joint linkages, I noticed that the skeleton of a regular 3-dimensional cube can be folded to a single edge (this can be achieved by first flexing the cube to bring it to a ...

3
votes

1
answer

104
views

### Does a matroid base polytope contain its circumcenter?

Let $(X,\mathcal B)$ be a matroid on the ground set $X=(x_1,...,x_n)$ and with set of bases $\mathcal B$, and let $P\subset\Bbb R^n$ be its matroid base polytope (i.e. the convex hull of the ...

6
votes

2
answers

258
views

### "Minimal" connected matroids

I'm interested in connected matroids $M$ on the ground set $[n]$ for which there is no connected matroid on $[n]$ of the same rank but with a strictly smaller set of bases (by inclusion). Equivalently,...

1
vote

0
answers

136
views

### References/applications/context for certain polytopes

First, let's consider an almost trivial notion. With any subspace $V\subset \mathbb R^n$ we associate a convex polytope $P(V)\subset V^*$ as follows. Each of the $n$ coordinates in $\mathbb R^n$ is a ...

0
votes

0
answers

38
views

### Basis of monoid of integral vectors

Suppose that $M\in\mathbb{Z}^{n\times k}$ is a matrix of rank $k<n$. How can I obtain a set of vectors $b_1,\ldots,b_k\in\mathbb{Z}^k$ (if exists) such that each row of $M$ is a non-negative ...

1
vote

0
answers

159
views

### Membership test of convex set

Let $K$ be a compact convex subset of $R^n$ which has some positive gaussian measure, say at least 1/2. For each nonzero vector $u \in R^n$, we
define another compact convex set $K * u$ in the ...

4
votes

2
answers

212
views

### On faces of polytopes

$\newcommand\ext{\operatorname{ext}}\newcommand\R{\mathbb R}$Let $A$ be a convex polytope in $\R^n$ with nonempty interior.
Consider the closed convex cone
$$K_A:=\{(l,t)\in(\R^n)'\times\R\colon\, l(x)...

0
votes

1
answer

98
views

### On the extreme points of two convex sets

Let $A$ and $B$ be two compact convex sets (which may be assumed to be polytopes) in $\mathbb R^n$ such that $A\cap B\ne\emptyset$. Is it then always true that either $A\cap\text{ext}B\ne\emptyset$ ...

1
vote

0
answers

60
views

### $\psi_2$ marginals of the permutahedron?

Let $K$ be a convex body.
I in particular care about the permutahedron.
I will view this as being the convex hull of all coordinate-wise permutations of the vector
$$v = \frac{1}{2n+2}(-n, -n+2,\dots, ...

1
vote

0
answers

75
views

### Factorising a multivariate polynomial, in terms of products of linear polynomials, using blowups

I am considering multivariate polynomials of the form
$$f(x,y)=x^a\,y^b\,p(x,y)^c$$
(and similarly for higher dimensions). I am trying to transform these polynomials into the generic form
$$\widetilde{...

8
votes

2
answers

370
views

### Permutohedron and triangulation of cube via Eulerian numbers

The $h$-vector of the (simplicial complex given by the boundary of the polytope dual to the) permutohedron is the sequence of Eulerian numbers $A(n,k)=\#\{w\in S_n\colon \mathrm{des}(w)=k\}$.
Example: ...

9
votes

1
answer

312
views

### The convex hull of Schur polynomial evaluations

Let $r\leq n$ and $d$ be positive integers. A probability vector is a vector of non-negative entries that sum to 1. For each probability vector $\lambda$ of length $n$, let
$$s(\lambda)=(\dim[\pi] \...

2
votes

0
answers

66
views

### Sampling theorems for partition polynomials (associahedra, noncrossing partitions / parking functions)

Define the associahedra partition polynomial
$$
\begin{split}
A(x) &= 1 + A_1(u_1) z + A_2(u_1,u_2) z^2 + A_3(u_1,u_2,u_3) z^3 + \cdots\\
& \qquad\qquad = 1 + \sum_{n \geq 1} A_n(u_1,...,u_n) ...

4
votes

0
answers

227
views

### How can we prove this combinatorial identity?

This is a follow up on my earlier MO post. Let's recall the sets
$$\mathbf{K}_n=\{\mathbf{k}\in\mathbb{Z}^n: k_i\geq0, k_1+\cdots+ k_n=n, k_1+\cdots k_i\leq i, \text{for all $1\leq i\leq n$}\}$$
and $\...

5
votes

1
answer

390
views

### Catalan sequences vs composition sequences

In the paper, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Pitman and Stanley studied the $n$-dimensional polytope
$$\Pi_n(\mathbf x)=\{y\in\...

4
votes

0
answers

51
views

### Quantifying error in the reconstruction of convex polytopes from moments

The problem of reconstructing a geometric object from its moments is of interest in a variety of fields. In the paper The Inverse Moment Problem for Convex Polytopes, the authors show that a convex ...

4
votes

1
answer

143
views

### Approximation of convex bodies by polytopes corresponding to smooth toric varieties

Let $P\subset \mathbb{R}^n$ be an $n$-dimensional polytope with rational vertices. There is a well known construction which produces an $n$-dimensional algebraic variety $X_P$ called toric variety. In ...

8
votes

1
answer

443
views

### Do this polyhedron and other set have names?

Updated: My first post had a mistake because I confused in my mind two different but related sets. Hopefully the description below is correct now.
Let $\Lambda$ be a finite set. Let $\Lambda^{(2)}$ be ...

1
vote

0
answers

52
views

### Fitting a convex polytope with 𝑛 facets between two nested spheres

This is related to a research problem that is interested in approximation of spheres by convex polytopes.
Let $C_r$ and $C_R$ be two spheres in $\mathbb R^d$ of radius $r$ and $R$, respectively, where ...

1
vote

0
answers

41
views

### About the number of faces of the conification of a polytope

Let $P\subset\mathbb{R}^n$ be a polytope of dimension $(n-1)$ such that the origin $\vec{0}\not\in\text{Aff}(P)$, where $\text{Aff}(P)$ denotes the affine hull of $P$ in $\mathbb{R}^n$. Now, we ...

2
votes

1
answer

72
views

### Example of worst case distributions for 4D convex hull

My understanding is that convex hull of n points in 4D could have O(n²) edges in the worst case. Source: https://sites.cs.ucsb.edu/~suri/cs235/ConvexHull.pdf
This same source writes
In 4D, there are ...