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
942 questions
1
vote
0
answers
29
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
1
vote
0
answers
124
views
Growth polynomial of the Associahedron graph ? (Is it approximately Gaussian ?)
Consider Associahedron, consider graph build from its vertices and edges. Choose some vertex. Let us count the number of vertices on distances $k$ from the selected vertex. Write a generating ...
- 24.9k
0
votes
0
answers
28
views
How to calculate the vertices of a convex polytope (k-DOP)
I am currently reading Christer Ericson's Real-Time Collision Detection Book. The topic I'm particularly interested in, is the chapter about Discrete-orientation Polytopes (k-DOPs). In his words "...
- 1
8
votes
0
answers
282
views
Meaning of the Ehrhart polynomial at $-1/2$?
I am studying a large collection of lattice polytopes, all of them being simple and empty. The dimension can be any integer. The dilatation by $2$ gives non-empty polytopes.
For many of these ...
- 3,587
1
vote
0
answers
57
views
Tiling with one of each 3D shape
Encouraged by the positive solutions to my question,
Tiling with one of each shape,
I'd like to pose the $\mathbb{R}^3$ equivalent:
Q. Is there a tiling of $\mathbb{R}^3$ by (bounded) polyhedra, one ...
- 151k
9
votes
0
answers
144
views
Which polytopes have compact realization spaces?
Let $P\subset\Bbb R^d$ be a convex polytope.
Its reduced realization space is the space of all combinatorially equivalent polytopes modulo projective transformations.
I am interested in polytopes for ...
- 13.6k
0
votes
0
answers
44
views
Lattice points in the boundary of a Minkowski sum of two convex lattice polygons
Let $P$ and $Q$ be two convex lattice polygons in $\mathbb{R}_+^2$ and let $P+Q$ be their Minkowski sum. Given a set $S \subset \mathbb{R}^2$, we let $L(S) =\#( S \bigcap \mathbb{Z}^2)$.
The equality $...
- 183
0
votes
0
answers
37
views
Constructing a minimum-volume outer approximation polytope with fewer facets
I am tackling the following problem:
Given a set of points $D \in \mathbb{R}^d$ and their convex hull, represented with $n$ facets, I want to construct a convex polytope $P$ with at most $m<n$ ...
- 101
6
votes
1
answer
347
views
Is a ball the hardest body to approximate by polytopes (in the Banach–Mazur metric)?
$\DeclareMathOperator\conv{conv}\DeclareMathOperator\Vol{Vol}$In the paper "An extremal property of the hypersphere" by Macbeath, the following functionals were introduced (here $n$ is fixed,...
- 93
1
vote
0
answers
72
views
Existence of a sequence of $-1/1$-polytopes with certain geometric properties
Let $P_n \subset \mathbb{R}^n$ be a sequence of polytopes (A polytope is the convex hull of finitely many points). Let $B_n \subset \mathbb{R}^{n}$ denote the Euclidean unit ball. I am interested in ...
- 93
3
votes
1
answer
239
views
A palindromic formula for simple convex polytopes
Let $P$ be a simple convex $d$-polytope (a $d$-dimensional convex polytope in which the number of edges incident to a vertex is $d$) and let $n_i$ be the number of $i$-faces of $P$. Is it true that ...
- 161
1
vote
0
answers
99
views
Shortest loop through vertices of a convex polytope
Let $P$ be a convex polytope in Euclidean space $\mathbf{R}^3$ and $\Gamma$ be a closed curve which passes through all vertices of $P$. How small can the length $L$ of $\Gamma$ be? More specifically, ...
- 7,169
0
votes
0
answers
69
views
Degree of reflectional symmetry of (unbounded) convex polyhedra in Euclidean spaces
Let $U \subset \mathbb{R}^m$ be an open domain. I'm trying to come up with a measure of its degree of reflectional symmetry and I have a question. The post in two-part, where in PART I I introduce the ...
- 1,467
0
votes
0
answers
81
views
A generalized permutohedron as the sum of the dilatations of the faces of the standard simplex
I am trying to understand the proof of the statement, specifically it refers to a theorem stated by Postnikov in his text on permutohedra. So, this sentence claims the following:
If $\{Y_I \}$ is a ...
- 251
2
votes
1
answer
147
views
Are there polytopes with precisely two realizations?
A convex polytope is projectively unique if it has a unique realization up to projective transformations. Such polytopes are somewhat mysterious but still well-studied. Examples are simplices, the ...
- 13.6k
1
vote
1
answer
200
views
Description of the generalized permutahedron
According to Postnikov, we know that the generalized permutahedron are describe as "polytopes obtained by moving vertices of the usual permutohedron so that directions of all edges are preserved&...
- 251
1
vote
0
answers
41
views
Is there any software package to find the vertices of convex polytope where the inequality constraints are bounded by variable?
I know of this package lcon2vert that computes vertices from given inequality and equality constraints describing a bounded polyhedron. Here the bounds of constraints only accept numerical values, i.e....
0
votes
0
answers
51
views
Minimizer of forward and reverse Kullback-Leibler divergence with sum constraints on marginals
Consider minimization of the Kullback Leibler divergence between two discrete distributions $p$ and $q$:
\begin{align*}
D_{KL} \left( p \parallel q \right) = \sum_i p_i \log \left( \frac{p_i}{q_i} \...
0
votes
0
answers
31
views
Group or semi-ring on polytope family
I want to determine how to provide structure to the polytope family; I guess the main article where this is discussed is the one by Peter Mcmullen entitled “The polytope Algebra”, here they talk about ...
- 251
2
votes
0
answers
318
views
What's the number of facets of a $d$-dimensional cyclic polytope?
A face of a convex polytope $P$ is defined as
$P$ itself, or
a subset of $P$ of the form $P\cap h$, where $h$ is a hyperplane such that $P$ is fully contained in one of the closed half-spaces ...
- 43
2
votes
0
answers
83
views
Is the volume of the image of the moment map an invariant of a symplectic toric manifold?
Given a symplectic toric manifold is known that the image of the moment map is a Delzant polytope that fully characterises the manifold. What about the volume of the polytope? Is it possible that two ...
0
votes
0
answers
116
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 ...
- 1
0
votes
0
answers
72
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
52
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 ...
- 101
10
votes
2
answers
255
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 ...
- 13.6k
3
votes
1
answer
239
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$ (...
- 13.6k
1
vote
1
answer
115
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 ...
- 45k
0
votes
1
answer
133
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 ...
- 161
4
votes
0
answers
46
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
103
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 ...
- 877
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 ...
- 5,979
1
vote
0
answers
114
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$, ...
- 1,804
13
votes
0
answers
378
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 ...
- 13.6k
0
votes
0
answers
78
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{...
- 3,064
7
votes
3
answers
704
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 ...
- 7,169
3
votes
0
answers
110
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 ...
- 31
2
votes
0
answers
64
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 ...
- 15.8k
6
votes
0
answers
199
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\...
- 809
0
votes
1
answer
172
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!
- 191
3
votes
0
answers
102
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
69
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 ...
- 131
3
votes
0
answers
151
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 ...
- 1,435
2
votes
1
answer
159
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 ...
- 275
4
votes
1
answer
181
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 ...
- 24.2k
3
votes
0
answers
124
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 ...
- 930
2
votes
0
answers
51
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}...
- 21
4
votes
1
answer
298
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 ...
- 13.6k
2
votes
1
answer
241
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, ...
- 123
3
votes
1
answer
42
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 ...
- 300
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 ...
- 1,305