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
5
votes
1
answer
349
views
What is the lower bound for the number of facets that a general convex $d$-polytope with $n$ vertices can have?
I am familiar with Barnette's Lower Bound Theorem on the number of facets a $d$-dimensional simplicial convex polytope with $n$ vertices can have. Is there a similar result for a general (i.e. not ...
- 53
0
votes
1
answer
117
views
Closed form solutions for maximal subsets of convex polytopes
I'm looking for any known exact results about inscribing simple convex bodies inside a convex polytope. The most famous is the Löwner-John ellipsoid, but as far as I understood in general there is no ...
- 445
2
votes
0
answers
78
views
An implementation of Minkowski reconstruction in 3 dimensions
By a theorem of Minkowski from 1903, an $n$-dimensional polytope $P\subset \mathbb R^n$ is determined up to translation by its unit face normal $u_1,\dots,u_k\in S^{n-1}$ and the corresponding $(n-1)$ ...
- 373
0
votes
0
answers
42
views
When is the set of faces of a convex polytope algebraically independent?
This is related to another question of mine
Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in ...
- 3,079
3
votes
0
answers
102
views
The ring generated by a convex polytope and its faces
Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in $V$ with multiplication induced by Minkowski ...
- 3,079
1
vote
1
answer
106
views
Linear relations between volume of a polytope and its faces
Let $P$ be a polytope. Is anything known about the set of linear relations that hold between the volumes of the (not-necessarily proper) faces of $P$ as $P$ “varies slightly”? By varies slightly I ...
- 3,079
3
votes
1
answer
258
views
Polygon of convex arcs
Convex polygons in the plane $R^2$ arise in linear programming where the constraints are linear. The objective linear function attains its maximum at a vertex of the feasible region(if exists).
Assume ...
- 422
7
votes
1
answer
1k
views
Minkowski sum of polytopes from their facet normals and volumes
By Minkowski's work in the early 1900s, every polytope $P\subset\mathbb R^n$ is determined up to translation by its unit facet normals $u_1,\dots,u_k$ and facet volumes $\alpha_1,\dots,\alpha_k$. ...
- 373
1
vote
0
answers
41
views
Possible volumes of lattice polytopes
All polytopes here are assumed to be convex lattice polytopes.
Given a polytope $P$, set $$v(P):= (\operatorname{vol}(F))_{F\text{ a face of }P},$$ where the volume of a $d$-dimensional polytope $P\...
- 3,079
10
votes
2
answers
224
views
The set of polytopes with given $f$-vector
Let $f=(f_0,\ldots f_n)$ be a vector in $\Bbb N^{n+1}$. Let $X$ be the set of all (ordered) $f_0$-tuples in $\Bbb R^n$ whose convex hull has $f$ as its $f$-vector. Assume that $X$ is non-empty. Is ...
- 3,079
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 ...
- 52.3k
8
votes
4
answers
1k
views
What is the probability distribution of the $k$th largest coordinate chosen over a simplex?
Suppose we're selecting points uniformly at random from the $N$-simplex
$S_N = \{x \in \mathbb R^{N+1}: $ all $ x_i \ge 0$ and $x_1 + \ldots x_N = 1\}$.
One way to do this in practice is choose $N-...
- 1,955
3
votes
0
answers
84
views
condition on rational polyhedral cone to guarantee dual cone is homogeneous
Let $\sigma\subseteq \Bbb R^d$ be a full-dimensional rational polyhedral cone which is strongly convex (i.e. $\sigma\cap-\sigma=0$).
Definition. The cone $\sigma$ is homogeneous if there are ...
- 3,079
18
votes
2
answers
573
views
Can the graph of a symmetric polytope have more symmetries than the polytope itself?
I consider convex polytopes $P\subseteq\Bbb R^d$ (convex hull of finitely many points) which are arc-transitive, i.e. where the automorphism group acts transitively on the 1-flags (incident vertex-...
- 13.6k
2
votes
0
answers
111
views
Can computers take uniform samples from a polytope?
For each $r \in \mathbb N $ write $\mathbb Z/ 10^r = \{a/10^r: a \in \mathbb Z\}$ and $P(r)$ for the lattice $(\mathbb Z/10^r)^N \subset \mathbb R^N$.
Suppose the plane $P \subset \mathbb R^N$ is ...
- 1,955
3
votes
2
answers
172
views
Maximal edge length of symmetric polytopes
For me, a polytope is the convex hull of finitely many points. It is said to be vertex-transitive / edge-transitive if its symmetry group acts transitively on its vertices / edges. Let's call a ...
- 13.6k
2
votes
1
answer
140
views
Separation of two pointed polyhedral cones using hyperplanes generated by facets
Let $C_1$ and $C_2$ two pointed (that is, with vertex in $0$) polyhedral cones in $\mathbb{R}^n$ with $\dim(C_1)=\dim(C_2)=n$. If
$$\mbox{relative interior}(C_1)\cap \mbox{relative interior}(C_2)=\...
- 131
4
votes
1
answer
380
views
Mathematical Structure and Objects Induced by Pairs of Disjoint Subsets
Let $\mathcal{S}$ be a finite, discrete and non-empty set, i.e.,
$$\begin{align} \operatorname{card}\left(\mathcal{S}\right) & =:n\in\mathbb{N}^+\\ V& :=\{v\subset\mathcal{S}\ |\ v\ne\...
- 13.2k
4
votes
2
answers
734
views
Fast projection onto a subspace
Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...
- 1,677
2
votes
0
answers
184
views
Can projecting a simplex onto orthogonal subspaces exposes the same vertices and edges?
Given the regular $n$-dimensional simplex $S\subset\Bbb R^n$ with $n\ge 4$, as well as two orthogonal subspaces $V,W\subset\Bbb R^n$ of dimension $\ge2$ (not necessarily of same dimension, not ...
- 13.6k
8
votes
2
answers
392
views
Can two non-equivalent polytopes of same dimension have the same graph?
By a polytope I mean the convex hull of finitely many points. The graph of a polytope is the graph isomorphic to its 1-skeleton. By equivalence of polytopes I mean combinatorial equivalence, i.e. ...
- 13.6k
8
votes
2
answers
1k
views
Is every polytope combinatorially equivalent to the intersection of a simplex and a linear subspace?
I wonder whether such a result is known, and if so, whether the proof is trivial.
By polytope I mean the convex hull of finitely many points in $\Bbb R^n$. Assume the simplex to be symmetric and ...
- 13.6k
1
vote
0
answers
74
views
How to minimize n-polytope's bounding box with linear transformation?
I am working on an exact algorithm for integer linear programming for my master's thesis:
$Ax\leq b, x \in \mathbb{Z}^n$
$cx\rightarrow min$
For my idea to work out, I need a guarantee that n-...
- 11
16
votes
3
answers
720
views
Can we realize a graph as the skeleton of a polytope that has the same symmetries?
Given a graph $G$, a realization of $G$ as a polytope is a convex polytope $P\subseteq \Bbb R^n$ with $G$ as its 1-skeleton.
A realization $P\subseteq \Bbb R^n$ is said to realize the symmetries of $...
- 13.6k
2
votes
0
answers
51
views
2-dimensional smooth lattice polytopes with minimal edge lengths
For each integer $k \geq 3$, does there exist a full-dimensional, $2$-dimensional, smooth lattice polytope $P$ with $k$ edges, such that each edge contains only two lattice points (i.e. only its ...
- 197
1
vote
0
answers
92
views
Simple polytope with smooth facets
Let $P$ be a simple $3$-dimensional (and full-dimensional) lattice polytope such that every facet $F$ is a smooth polytope. Is then $P$ itself smooth?
EDIT: A full-dimensional lattice polytope $P$ is ...
- 197
1
vote
0
answers
69
views
Can sufficiently symmetric polytopes be uniquely reconstructed from their 1-skeleton?
General convex polytopes can not be uniquely reconstructed from their 1-skeleton1, as explained here. Not even the dimension is known from the skeleton, as e.g. the complete graph $K_n,n\ge 5$ is the ...
- 13.6k
4
votes
1
answer
516
views
Is the preimage of a face under an affine map a face?
Let $X\subseteq\mathbb{R}^n$ be a convex set. Let $\pi{:}\ X\to\mathbb{R}^m$ be a linear map, with $m<n$ (for example, a projection). Let $\pi^{-1}(y)=\{x\in X\mid\pi(x)=y\}$ denote the inverse of $...
- 75
8
votes
1
answer
497
views
Higher dimensional scutoids?
The recent discovery of scutoids in biological structures is fascinating. Two scutoids are depicted below (from Scientists Have Discovered an Entirely New Shape, And It Was Hiding in Your Cells), each ...
- 10.5k
6
votes
1
answer
133
views
How rich is the class of vertex- and edge-transitive polytopes?
There are only a few regular polytopes (five in 3D, six in 4D, three in any dimension above). In contrast, the class of uniform polytopes becomes very rich with higher dimensions.
The class of vertex-...
- 13.6k
4
votes
2
answers
535
views
Complexity of 2D-Minkowski sum of non-convex polygons
I have read that the complexity of computing the Minkowski-Sum of $2$ non-convex polygons (through convex decomposition) is $O(m^2 n^2)$, where $m$ and $n$ is the number of vertices of each polygon. ...
4
votes
1
answer
141
views
Continuity of the combinatorial structure of a polytope with respect to face variables
Suppose we are given a convex polytope in terms of the face variables.
That is, let $Y = (1,x_1,\dots,x_n)$ and suppose we have vectors $W_a$ in $\mathbb{R}^{n+1}$ such that the locus $W_a \cdot Y \...
- 1,435
8
votes
0
answers
274
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 ...
- 4,679
4
votes
0
answers
210
views
Conjecture on tilting modules for an Auslander algebra
On page 13 of "Tilting modules for the Auslander algebra of $K(x)/x^n$" the author, Geuenich, suggests that the number ($p_{n,i}$) of isomorphism
classes of modules, occurring as the $i$-th summand of ...
- 10.5k
6
votes
1
answer
274
views
Example of convex n-gon that cannot be decomposed into k congruent convex polygons
I asked a related question here on MO without any answers yet.
The question is in the title - give an example of a convex $n$-gon that cannot be subdivided into $k>1$ congruent convex polygons.
...
- 15.8k
0
votes
0
answers
165
views
Probability that the perturbed convex hull is larger than the original one
I am wondering if any convex geometers/probabilists have looked at the following question:
Given $n$ randomly distributed (not sure what assumption to put there) points in $\mathbb{R}^d$, for each ...
- 133
-1
votes
2
answers
114
views
On OR condition in Linear Programming with exponentially many constraints [closed]
Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
- 13.9k
9
votes
3
answers
461
views
Minimal combinatorial data needed to define a polytope [duplicate]
Suppose I give a list of vertices $(v_1, v_2, ..., v_n)$, and a list of "adjacencies", i.e. pairs of vertices $(v_i,v_j)$. Does it exists a unique polytope that has this vertices and realises the ...
- 1,435
1
vote
0
answers
47
views
What separates a cyclic polytope from a projective polytope?
I am having trouble understanding the difference between a cyclic polytope and a convex projective polytope as positive geometries.
The link https://arxiv.org/pdf/1703.04541.pdf is the source of ...
- 151
6
votes
1
answer
298
views
Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?
In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...
- 155
3
votes
0
answers
181
views
Refined f- and h-partition polynomials of the associahedra
The f-polynomials, $F_n(x)$ (cf. OEIS A126216, A033282, and A086810), and the h-polynomials, $H_n(x)$ (cf. A001263, the Narayana polynomials), of the family of simple convex polytopes the associahedra ...
- 10.5k
2
votes
0
answers
41
views
Efficient $H$ representation of matrices with distinct cyclic shift permuted entries
Given points $v_1,\dots,v_n\in\mathbb Z^n$ in codimesion $1$ hyperplane $x_1+\dots+x_n=t$ with $0\leq x_{i}$ and a cyclic shift permutation $\sigma$ where
$v_1,\dots,v_n$ when written as columns of ...
- 13.9k
7
votes
2
answers
268
views
How different can the constituents of an Ehrhart quasi-polynomial be?
Consider a $d$-dimensional convex rational polytope $P\subset\mathbb{Q}^d\subset\mathbb{R}^d$. Then, it's a standard fact that in general the function counting the number of lattice points inside the ...
- 650
1
vote
1
answer
266
views
Relative interior of a normal cone at a face of a convex polytope?
Suppose $A$ is a nonempty convex polytope in $\mathbb{R}^n$. Suppose $F$ is a face of $A$.
Consider the normal cone of $A$ at $F$:
$C_A(F)=\{v\in\mathbb{R}^n:v\cdot x\geq v\cdot y\ \forall\ x\in ...
- 159
3
votes
1
answer
263
views
Size of a minimal non-negative conic basis
Suppose $v_1,\dots,v_n \in \mathbb{R}^k$ are entry-wise non-negative (column) vectors with $k<n$. Let $r \leq k$ be the non-negative rank of the matrix $V = [v_1 v_2 \cdots v_n]$ (i.e., the ...
9
votes
2
answers
763
views
Parallelepiped is defined by the volumes of its faces
Let $v_1,...,v_n\in \mathbb{R}^n$ be linearly independent. The parallelepiped defined by these vectors is $P(v_1,...,v_n)=\{\sum_{i=1}^{n}\alpha_i v_i|~0\le\alpha_i\le 1\}$. Observe that while the ...
- 5,529
6
votes
1
answer
254
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 ...
- 7,194
10
votes
1
answer
483
views
Odds on rolling a rhombicosidodecahedron
This is more of a curiosity to me, but I'm sure I don't have the mathematical skills to answer it. That said... I took a look at several other posts with questions that relate to this one, but I ...
- 103
2
votes
1
answer
349
views
Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?
Sorry the title may be unclear. I do not know how to give it a good title.....
Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
- 159
0
votes
0
answers
369
views
Finding a point in the relative interior of the convex hull of a set of integer-valued vectors
Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
- 136