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
918
questions
55
votes
1
answer
3k
views
Intersecting family of triangulations
Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
4
votes
0
answers
212
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 ...
4
votes
1
answer
181
views
2-faces of reflexive Delzant polytopes
Question 1. Can a reflexive Delzant polytope of some dimension contain a $2$-face with more than $11$ edges?
Motivation. I would like more generally to get an answer to the following question:
...
4
votes
4
answers
531
views
Vertex-transitive polytopes in any dimension with any number of vertices?
Given positive integers $d$ and $v$ with $v \geq d+1$, does there always exist a (convex) vertex-transitive $d$-polytope with $v$ vertices? It seems that the answer should be "obviously" true, but I ...
11
votes
1
answer
670
views
Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable?
According to this source (p. 10), determining whether a simplicial complex is a simplicial sphere (the sphere recognition problem) is undecidable.
According to this source, determining whether a ...
19
votes
2
answers
1k
views
About a Delzant polytope. (In particular dodecahedron)
Hi. I have a question.
Definition. Delzant polytope $P$ is a rational convex simple polytope with the smooth condition. Here, "smooth" means that for each vertex $v$, the $n$ edges containing $v$ ...
4
votes
2
answers
536
views
Secondary polytope
Given a polytope $P$, what do the points of the secondary polytope correspond to?
I know that the vertices of the secondary polytope correspond to regular triangulations of $P$.
But what do the ...
4
votes
2
answers
253
views
A rational polytope that is not a 01-polytope?
A 01-polytope is the convex hull of some points $S\subseteq\{0,1\}^n$. I wonder, which polytopes can be represented (combinatorially) as 01-polytopes? There are polytopes that cannot have rational ...
16
votes
1
answer
478
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
vote
0
answers
43
views
Barnes-Wall lattices’ contact polytopes
The contact polytopes of the Barnes-Wall lattices in 1, 2, 4, and 8 dimensions are all uniform polytopes. Is this true in any higher number of dimensions?
2
votes
1
answer
284
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\...
2
votes
1
answer
122
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-...
23
votes
1
answer
654
views
Covering the unit sphere in $\mathbf{R}^n$ with $2n$ congruent disks
Let $v_i$ be $2n$ points in $\mathbf{R}^n$, with equal distance $|v_i|$ from the origin. Suppose that the convex hull of these points contains the unit ball. Is it known that $|v_i|\geq\sqrt{n}$? ...
18
votes
1
answer
630
views
Known configurations maximizing the volume of the convex hull of n points on the unit sphere
For $n\geq 4$, let $V_n$ be the maximum volume of the convex hull of $n$ points on the unit sphere (in $\mathbb{R}^3$, although information on higher dimensions is welcome as well). I'm sure the ...
3
votes
1
answer
183
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 ...
8
votes
1
answer
311
views
Inscribed $n$-polytope with $2^n$ vertices of maximal volume
The question is in the title:
Question: Which inscribed $n$-dimensional polytope (inscribed in the unit sphere) with $2^n$ vertices has the largest possible volume?
Is it the $n$-dimensional cube? ...
11
votes
0
answers
297
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 ...
15
votes
1
answer
684
views
Information inequalities
What are the feasible $2^n$-tuples of entropies $h(S) := H(X_{i_1},\dots,X_{i_{|S|}})$ where $X_1,\dots,X_n$ are discrete random variables with some (unknown) joint probability distribution as $S=\{...
2
votes
0
answers
49
views
Endpoints of intrinsic diameter of a convex polyhedron
Let $P$ be a convex polyhedron in $\mathbb{R}^3$, and $d(P)$ its intrinsic diameter,
i.e., the longest shortest surface path between two points. Say that $P$ is of
class
$D_0$ if neither endpoint of $...
8
votes
1
answer
320
views
Monge-Ampère measures and Kazarnovskii pseudovolume
Let $\Gamma\subset\mathbb C^n$ be a convex polytope and let $h_\Gamma(z)=\max_{v\in\Gamma}{\rm Re}\langle z,v\rangle$ be its support function with respect to the standard scalar product on $\mathbb C^...
4
votes
1
answer
144
views
A combinatorial characterization of the central inversion of a polytope?
Given a convex full-dimensional polytope $P\subset\Bbb R^d$ (convex hull of finitely many points and not contained in any proper affine subspace) and a symmetry thereof (a linear map $\smash{T\in\...
3
votes
2
answers
341
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?
16
votes
5
answers
1k
views
A characterization of convexity
While doing some research on polytopes I came to the following question. Maybe it's already somewhere but anyway I'll post it here.
Let $X\subset \mathbb{R}^3$ be such that, for every plane $P$, $P\...
44
votes
11
answers
25k
views
Algorithm for finding the volume of a convex polytope
It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
18
votes
3
answers
2k
views
Guises of the Stasheff polytopes, associahedra for the Coxeter $A_n$ root system?
Richard Stanley keeps a famous running compilation of different guises of the celebrated Catalan numbers. The number of vertices of the associahedron is one instantiation among the multitude, and the ...
4
votes
1
answer
181
views
What is the convex cone generated by the pair of rank 1 matrix and its eigenvector?
I'd like to know what is the convex cone generated by $\left\{ (h h^T, h) : h \in \Bbb R^{d\times1} \right\}$. It is known that $$\mathrm{cone} \left\{h h^T : h \in \Bbb R^{d \times1} \right\} = S_+^d$...
5
votes
1
answer
448
views
Polynomial size embeddings of toric varieties from polytopes?
Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan.
$X_P$ is always projective, because the collection of characters corresponding to the points $\...
4
votes
2
answers
3k
views
Break polyhedron into tetrahedron
Given a polyhedron consists of a list of vertices (v), a list of edges (e), and a list of surfaces connecting those edges (...
1
vote
1
answer
93
views
Volume ratio of polytopes with few vertices
The volume ratio of a convex body $K\subset \mathbb{R}^{n}$ is $v_r(K) = \inf_{\mathcal{E}\subset K} \left(\frac{Vol(K)}{Vol(\mathcal{E})}\right)^{1/n}$ where the infimum run over ellipsoids included ...
24
votes
1
answer
724
views
Given a group action on a simplex, can I always find a fundamental region that is a simplex?
Let $\Delta\subset\Bbb R^n$ be a simplex with $n+1$ vertices. Let $G\subset\mathrm{GL}(\Bbb R^n)$ be a finite group of linear symmetries of $\Delta$, i.e. linear transformations that fix the simplex ...
22
votes
1
answer
676
views
Rational inscribed realization of the regular dodecahedron
While it is clear that the regular dodecahedron $D$ cannot be realized with all integer coordinates, it is easy to find a polytope, which is combinatorially equivalent (face lattice isomorphic) to $D$ ...
3
votes
0
answers
145
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} ...
4
votes
1
answer
111
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 ...
14
votes
2
answers
444
views
Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?
For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices
$$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\
\pi_{2,1} & \ddots & \...
11
votes
2
answers
1k
views
Which (semi)regular polyhedra are combinations of two others?
The convex combination of convex polytopes is a convex polytope.
An example in $\mathbb{R}^2$ is that a regular octagon
can be obtained as $\frac{1}{2} S + \frac{1}{2} S'$,
where $S$ is a square and $...
3
votes
0
answers
92
views
Simplex cover of an n-cube with non-congruent simplexes
I am curious about simplex coverings of the unit n-dimensional hypercube (or n-cube) with the following properties:
The simplexes do not need to be regular
The simplexes can be non-congruent (i.e. of ...
1
vote
0
answers
151
views
Volume of a polytope as its degenerates to be lower dimensional
Consider a polytope $P$ defined by the usual inequalities $A\mathbf{x}\leq \mathbf{b}$; let me assume that $P$ is not contained in a proper subspace. A result which I believe to true, but am not ...
4
votes
1
answer
284
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 ...
4
votes
1
answer
171
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{...
1
vote
1
answer
83
views
Can upper bounds on totally monotone functions be taken (WLOG) to be themselves totally monotone?
Consider the following: fix a function $\bar{b} : \mathbf{R}_+ \to [0, \infty]$, and define
\begin{align}
\mathcal{S} \left( \bar{b} \right) := \left\{ b : \mathbf{R}_+ \to [0, \infty] \, \text{s.t.} \...
13
votes
1
answer
496
views
Can you perturb an inscribed polytope so all its edges grow?
Consider the family of convex simplicial polytopes with vertices in the unit sphere of $\mathbb{R}^n$ which have the origin as an interior point.
My question is the following:
Let $P, P'$ be two non-...
1
vote
0
answers
28
views
Adjacent vertices of a permutohedron which is the orbit of a point $x$ with repeated coordinates
Question: Let $x=(x_1, ..., x_n) \in \mathbb{R}^n$, and let $P$ be the convex hull of the points formed by permuting the coordinates of $x$. Given a vertex $y$ of $P$, what is a general rule for ...
7
votes
2
answers
967
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
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 ...
0
votes
0
answers
115
views
Graduate level convexity - Intersection of an r-polytope with a hyperplane is an r-1 polytope
I am trying to follow Roger Webster's Convexity 's proof of Euler's celebrated result on the relationship between the number of faces of a polytope. An image of the proof is here.
In the course of the ...
31
votes
2
answers
2k
views
The logic of convex sets
Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so ...
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 ...
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 ...
1
vote
0
answers
56
views
Are cells of 4-polytopes a convex polyhedron by definition?
I'm going by the Wikipedia definition for a 4-polytope.
Do by definition, cells of 4-polytopes have to be a convex polyhedra?
If not, then are there polyhedra with non-convex faces?
If yes, is it the ...
20
votes
4
answers
910
views
The limit of edge-midpoint convex polyhedra
Starting with a convex polyhedron $P_1 \subset \mathbb{R}^3$,
replace that with $P_2$, the convex hull of the midpoints of the edges of $P_1$.
Continuing this process, we obtain a ...