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
4
votes
1
answer
290
views
Intrinsic definition of a cone in a normal fan
Let $P\subseteq \mathbb{R}^n$ be a full dimensional polytope. Let us assume that $P$ has a facet description with the following inequalities:
$$ \left<x,u_F\right> \geq -a_F$$
where $u_F\in \...
- 1,889
10
votes
3
answers
500
views
Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increases in length, can the circumradius still get larger?
Let $P\subset \Bbb R^n$ be an inscribed convex polytope, that is, all its vertices are on a common sphere of radius $r$.
Let $G$ be the edge-graph of $P$. For convenience, assume $V(G)=\{1,\dotsc,s\}$....
- 13.6k
2
votes
1
answer
308
views
Intersection of the simplex with a linear subspace of codimension $2$
The sets are defined in $\mathbb{R}_+^n$ $(n\geq 1)$. The relative interior of a convex set $C$ is denoted $\mathring C$.
Let $S$ be the $n$-simplex:
$$S=\left\{x\in\mathbb{R}_+^n,\,\sum_{i=1}^n x_i=1\...
- 449
63
votes
8
answers
14k
views
Fair but irregular polyhedral dice
I am interested in determining a collection of geometric conditions that will guarantee that a convex polyhedron
of $n$ faces is a fair die in the sense that, upon random rolling, it has an equal $1/n$...
- 151k
4
votes
0
answers
224
views
Characterization of curves contained in the boundary of convex bodies
Given a continuous closed curve $\gamma$ in $\mathbb R^n$ does there exist a convex body $K$ (convex set with non-empty interior) such that $\gamma\subset \partial K$?
I am looking for a reference to ...
3
votes
0
answers
187
views
Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets
Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
- 1,677
1
vote
0
answers
136
views
Which vector configurations generate as zonotope the regular $2n$-gon?
For $X=(x_1,\dots,x_n) \in (\mathbb{R}^2)^n$, the generated zonotope (zonogon in 2D) is defined by
$ Z(X) := \{\sum_{k=1}^n \sigma_k x_k
: \sigma_1,\dots,\sigma_n \in [0,1] \}. $
Which $X$ ...
- 101
10
votes
3
answers
322
views
Integer decomposition property with a partial order
Let $\mathcal{P}$ be a convex lattice polytope in $\mathbb{R}^n$. We say that $\mathcal{P}$ has the integer decomposition property (or "is IDP") if for all $k\in \mathbb{N}$ and $\alpha \in ...
- 24.2k
0
votes
1
answer
101
views
Maximum number of vectors with bounds on inner products (follow up question)
This is a follow-up question from my previous question.
Suppose there are (2n+1) vectors $\{m_1,m_2,...,m_n\}$, $\{p_1,p_2,...,p_n\}$ and $p^*$ in $R^{k+1}$. $m_i$ are weakly positive vectors. $p_i$ ...
- 23
11
votes
0
answers
329
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 ...
- 171
1
vote
0
answers
73
views
Polytope of a projected toric variety
I was looking for such a result in the book by Cox, Little and Schenck but I'm not able to find a proper reference.
All of the following requirements are tacitly assumed to be in the projective ...
- 1,343
7
votes
0
answers
162
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 \...
- 1,677
3
votes
1
answer
218
views
Bounding the number of facets of a polytope to approximate a given convex shape in higher dimensions
We are given a convex shape $S$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume $V(S)$ of $S$ be $\tfrac12$ (I guess nothing changes for any other fixed ...
- 1,677
4
votes
1
answer
304
views
Do combinatorially equivalent polytopes have the same triangulations?
A triangulation of a convex polytope $P\subset\Bbb R^n$ is a partition of $P$ into $n$-simplices $\{\Delta_1,...,\Delta_m\}$ each of which has all its vertices among the vertices of $P$. A polytope ...
- 13.6k
16
votes
1
answer
508
views
Can solutions to Thomson's problem have pentagons?
Thomson's problem asks for the minimum-energy configuration for $N$ electrons on a sphere (refs: https://en.wikipedia.org/wiki/Thomson_problem, https://sites.google.com/site/adilmmughal/...
- 1,203
4
votes
0
answers
52
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 ...
- 181
27
votes
3
answers
13k
views
Which unfoldings of the hypercube tile 3-space: How to check for isometric space-fillers?
Recently Mark McClure constructed and displayed
the 261 unfoldings of the hypercube (tesseract)
in response to the question,
"3D models of the unfoldings of the hypercube?":
The first 9 unfoldings ...
- 151k
19
votes
1
answer
928
views
Can every simple polytope be inscribed in a sphere?
It is known that not every convex polytope (even polyhedron, e.g. this one) can be made inscribed, that is, we cannot always move its vertices so that
all vertices end up on a common sphere, and
the ...
- 13.6k
1
vote
0
answers
110
views
Upper bound on the diameter of a convex lattice n-gon with a given area
Given the area $A$ of a strictly convex polygon with $n$ vertices with integer Cartesian coordinates, there are usually several non-equivalent polygons. The relationship between the area, the number ...
- 206
24
votes
1
answer
1k
views
Which unfoldings of the $d$-dimensional hypercube tile $(d{-}1)$-space?
A six year old question,
Which unfoldings of the hypercube tile $3$-space?, has just been answered by
Moritz Firsching:
All $261$ unfoldings tile space!
So now we know:
For $d=2$, the unfolding of ...
- 151k
2
votes
0
answers
94
views
Is it possible to deduce Poincaré duality from duality of polytopes?
I'm having trouble understanding Poincaré duality, as it seems unmotivated. Here for instance:
https://math.stackexchange.com/a/14469/454016
Poincaré duality is explained through a duality of ...
2
votes
1
answer
137
views
What does the boundary of convex hulls look like in matrix Lie groups?
Let $G$ be a compact matrix Lie group under the Killing form metric $\langle \xi, \eta \rangle_g = -\frac{1}{2}\text{tr}((g^{-1}\xi)^T(g^{-1}\eta))$ for $g \in G$ and $\xi,\eta \in T_gG$. Let $C \...
- 518
3
votes
0
answers
67
views
maximizing number of lattice points with bounded diameter
Suppose I have a lattice $L$ that's just $\mathbb{Z}^k$ but scaled in every coordinate by some (potentially different) real numbers. Now I want to construct a finite set of lattice points $S \subset L$...
- 480
6
votes
1
answer
277
views
Realizing spherical complexes as convex polytope
A spherical polytope is the intersection of some closed hemispheres which is non-empty and does not contain a pair of antipodal points. A spherical complex is a tiling of the whole (d−1)-dimensional ...
- 305
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 ...
- 131
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
15
votes
4
answers
856
views
Convex bodies have more volume on the outside near the boundary
I am looking for a reference for a result from convex geometry that I suspect has already been proven. The result seems geometrically obvious, but I couldn't find a similar result in Peter Gruber's ...
- 403
1
vote
0
answers
100
views
All 3-dimensional symmetric reflexive polytopes
$\DeclareMathOperator\Conv{Conv}$I am finding all 3-dimensional symmetric reflexive polytopes. To do so, first, we know that all 2 dim symmetric reflexive polytopes are $X_3=\Conv((-1,-1),(1,0),(0,1))$...
- 21
1
vote
0
answers
61
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
1
answer
75
views
Fixed points of rational continuous piecewise affine maps
Say that a compact convex polytope is rational if is the intersection of half-spaces whose bounding hyperplanes are the zero-sets of affine functions of the coordinates with rational coefficients. Say ...
- 19.7k
4
votes
1
answer
117
views
Given a polytope $P$ with bipartite edge-graph, if the bipartition classes are equal in size and lie on spheres, is $P$ inscribed?
Suppose that $P\subset\Bbb R^n, n\ge 3$ is a (full-dimensional) convex polytope with a bipartite edge-graph $G=(V_1\cup V_2,E)$ (for example, a zonotope). Suppose further that there are concentric ...
- 13.6k
4
votes
1
answer
194
views
How to solve this minimax matrix optimization problem?
Recently, I want to know how well can a $\ell_1$ ball be approximated by the image of a $\ell_2$ ball under a linear transform. I formulate this problem as the following optimization problem.
\begin{...
- 550
8
votes
1
answer
1k
views
Two questions on the permutohedron
The $n$-dimensional permutohedron $P_n$ is the polytope given by the convex hull of all the possible permutations of the vector $(1,2,\dots,n+1)\in\mathbb{R}^{n+1}$. So it has $(n+1)!$ vertexes.
I ...
user82886
26
votes
2
answers
4k
views
3D models of the unfoldings of the hypercube?
There are (apparently) 261 distinct unfoldings of the 4D hypercube, a.k.a., the
tesseract, into 3D.1
These unfoldings (or "nets") are analogous to the 11 unfoldings of
the 3D cube into the plane.2
...
- 151k
72
votes
2
answers
9k
views
The amplituhedron minus the physics
Is it possible to appreciate the geometric/polytopal properties of the amplituhedron without delving into the physics that gave rise to it?
All the descriptions I've so far encountered assume ...
- 151k
11
votes
0
answers
345
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 ...
- 2,537
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
3
votes
2
answers
438
views
If a polytope is centrally symmetric and combinatorially equivalent to a zonotope, is it a zonotope?
A zonotope is a polytope whose 2-faces are centrally symmetric.
Question: If a polytope $P$ is centrally symmetric and combinatorially equivalent to a zonotope, is it itself a zonotope?
- 13.6k
21
votes
2
answers
8k
views
How many vertices can a convex polytope have?
One has an $n$-dimensional convex polytope $P$ represented by an intersection of half-spaces:
\begin{equation}H_i = \{ (x_1,x_2, \ldots,x_n) \in \mathbb{R}^n \mid \sum_{j=1}^n a_{ij} x_j \ge a_{i0}, \...
- 251
5
votes
2
answers
134
views
Is there a non-orthogonal linear deformation of a polytope that preserves edge-lengths and vertex-origin-distances?
Is there a polytope $P\subset\Bbb R^d$ (convex hull of finitely many points, not contained in a proper affine subspace), and a linear, but non-orthogonal transformation $T\in\mathrm{GL}(\Bbb R^d)\...
- 13.6k
7
votes
0
answers
227
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 ...
- 151k
1
vote
0
answers
36
views
Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?
Suppose that $P$ is a polyhedron represented by
$$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$
and $P$ contains interior points. Moreover, the ...
- 33
2
votes
1
answer
137
views
Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$
Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
- 6,853
36
votes
2
answers
2k
views
Bodies of constant width?
In two-dimensional case one can generalize figures of constant width as figures which can rotate in a convex polygon.
Here is one example which can be used to drill triangular holes:
I would like to ...
- 45k
55
votes
5
answers
2k
views
Do unit quaternions at vertices of a regular 4-simplex, one being 1, generate a free group?
Choose unit quaternions $q_0, q_1, q_2, q_3, q_4$ that form the vertices of a regular 4-simplex in the quaternions. Assume $q_0 = 1$. Let the other four generate a group via quaternion ...
- 22.3k
0
votes
4
answers
457
views
Confining a polytope to one side of an affine hyperplane
Judging whether one convex polytope is inside of another when both are expressed as a system of linear inequalities seems not to be an easy problem.
This answer on math.stackexchange.com claims the ...
- 2,239
4
votes
1
answer
172
views
Forbidden minor characterization of polytope skeletons
Say that a graph is "$d$-dimensional" if it is the node-disjoint union of $1$-skeletons of closed convex polytopes in $d$ dimensions, or a subgraph thereof. So the $2$-dimensional graphs are exactly ...
- 1,389
3
votes
0
answers
151
views
Permutahedra Euler characteristic polynomials from cumulant-moment relation, a combinatorial proof?
Given the formal Taylor series, or e.g.f.,
$f(x) = 1 + \sum_{n \geq 1} m_n \; \frac{x^n}{n!}$,
the classical formal cumulants $c_n$ are generated from the formal moments $m_n$ via
$ \sum_{n \geq 1} ...
- 10.5k
4
votes
2
answers
415
views
Selecting vertices in a convex polygon
Given $n$ vertices of a convex polygon in $\mathbb{R}^2$, selecting two points that are furthest apart is done by finding the diameter in a convex polygon. But how can one select three vertices such ...
- 51
15
votes
3
answers
1k
views
Classification of Platonic solids
My question is very basic: where can I find a complete (and hopefully self-contained) proof of the classification of Platonic solids? In all the references that I found, they use Euler's formula $v-e+...
- 955