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
2
votes
0
answers
63
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) ...
0
votes
1
answer
114
views
How can I find the hyperplane passing through a 600-cell
I have a 600-cell, whose coordinates are given by
$$\begin{array}{ccc}
\text{8 vertices} & \left(0,0,0,\pm1\right) & \text{all permutations,}\\
\text{16 vertices} & \frac{1}{2}\left(\pm1,\...
2
votes
2
answers
1k
views
Mathematical tools appropriate to analyse convex polyhedra
What mathematical tools (means: set of areas of mathematical knowledge) are appropriate to begin with to analyse (to enumerate face vectors associated with polyhedron, to calculate the combinatorial ...
4
votes
0
answers
218
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 $\...
4
votes
4
answers
704
views
Parametrizing the realization space of a polyhedron by its edges
I alluded to this here, but at that point I hadn't really done enough work to know what I wanted to ask.
Call a polyhedron "trihedral" if three faces meet at each vertex. Each of the F faces can be ...
5
votes
1
answer
389
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\...
5
votes
2
answers
3k
views
How to break a concave polyhedron into a few convex polyhedron?
I would like to know is there a way to break a concave polyhedron into a few convex polyhedron?
0
votes
0
answers
23
views
Approximation of connected set by triangluation / covering by simplices
Good afternoon. I have two distinct questions:
If I have connected compact in $\mathbb{R}^n$, how much $(n+1)$-simplices are needed to fill its interior such that diameter of maximal uncovered part ...
10
votes
1
answer
316
views
covering convex sets by round balls
Let $X=\{x_1,...,x_k\}\subset E^n$ be a finite subset in the Euclidean $n$-space, $r>0$ and $B(x_i,r)$ are open balls of radius $r$ centered at the points $x_i\in X, i=1,...,k$. Suppose that
$$
\...
4
votes
0
answers
46
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 ...
54
votes
3
answers
3k
views
The view from inside of a mirrored tetrahedron
Suppose you were standing inside a regular tetrahedron $T$ whose
internal face surfaces were perfect mirrors.
Let's assume $T$'s height is $3{\times}$ yours, so that your
eye is roughly at the ...
8
votes
1
answer
435
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 ...
4
votes
1
answer
136
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 ...
1
vote
0
answers
48
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 ...
2
votes
3
answers
2k
views
Better tactics for removing redundant constraints than Linear Programming?
After reading:
Detection of Redundant Constraints
It appears that linear-programming is the most commonly known way to remove ALL redundant constraints from a system of inequalities of the form
$$ ...
13
votes
2
answers
3k
views
How many vertices/edges/faces at most for a convex polyhedron that tiles space?
I wonder if this problem has already been examined before:
Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have?
...
1
vote
0
answers
39
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
65
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 ...
1
vote
0
answers
26
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 ...
1
vote
0
answers
59
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 ...
4
votes
2
answers
241
views
Does the edge-graph of a centrally symmetric polytope determine which vertices are antipodal?
Given two origin symmetric convex polytopes $P_1$ and $P_2$ (that is $P_i=-P_i$) with the same edge-graph, but potentially of different dimensions and combinatorial types.
Let $\phi: G_{P_1}\to G_{P_2}...
5
votes
2
answers
130
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)\...
3
votes
0
answers
56
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$...
0
votes
1
answer
88
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$ ...
1
vote
1
answer
191
views
Maximum number of vectors with bounds on inner products
Suppose there are 2n vectors $\{m_1,m_2,...,m_n\}$ and $\{\mu_1,\mu_2,...,\mu_n\}$. All vectors are in k-dimensional Euclid space $R^k$. The vectors satisfy:
$$m_i \mu_j \leq 0, \quad \forall i\neq j $...
5
votes
1
answer
213
views
Proof of Lemma 37.5 in Pak's Lectures on Discrete and Polyhedral Geometry
I am staring at the proof of Lemma 37.5 in Lectures on Discrete and Polyhedral Geometry, see page 331.
I cannot understand why the required triangulation exists.
In the first paragraph it says "...
18
votes
2
answers
557
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-...
2
votes
0
answers
200
views
Toric decomposition of multipartitions
Fix $k \in \mathbb Z_{>0}$. By a $k$-multipartition $\lambda=(\lambda_1,\dots,\lambda_k)$ of $N$, I mean that each $\lambda_i$ is a partition of some $N_i$ and $\sum N_i = N$.
Let's call $\lambda$ ...
2
votes
1
answer
135
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 \...
4
votes
0
answers
130
views
Can a polytopal graph be "centrally symmetric" in more than one way?
Let $P,Q$ be two centrally symmetric convex polytopes, potentially of different dimensions and combinatorial type, but with the same edge-graph $G$.
The central symmetry of $P$ induces an involutory ...
2
votes
0
answers
82
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 ...
1
vote
1
answer
1k
views
The stock market polytope: explanation?
Ovidiu Racorean.
"Crossing stocks and the positive Grassmannian I: The Geometry behind Stock
Market."
(arXiv Abstract link)
Anyone care to offer a summary of what's going on here?
(The ...
18
votes
3
answers
2k
views
Are the Platonic solids shadows of 4-polytopes?
Say that a 3D shadow of a 4-polytope is a parallel projection to 3-space, not necessarily orthogonal to that 3-space (that would make it an orthogonal projection).
I am wondering if each of the five ...
1
vote
0
answers
125
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$ ...
5
votes
2
answers
201
views
Topology of a union of facets of a convex polytope
The following question arose from a survey paper I am writing on
combinatorial reciprocity. Let $\mathcal{P}$ be a $d$-dimensional
convex polytope. Let $\mathcal{Q}$ be a union of facets (codimension
...
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 ...
3
votes
3
answers
308
views
4-polytope with vertices at the binary octahedral group
Does anybody know if there is a convex polytope in $R^4$ with vertices at the binary octahedral group (identifying $H$ with $R^4$).
The binary tetrahedral group lies at the vertices of the so-called ...
1
vote
1
answer
70
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 ...
10
votes
3
answers
310
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 ...
6
votes
2
answers
633
views
A convex polyhedral analog of the pentagram map
I am wondering if there is a three-dimensional analog of
the pentagram map, which maps a convex polygon to another
convex polygon. Here's the Wikipedia image:
I am seeking something similar that maps ...
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 ...
15
votes
4
answers
810
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 ...
2
votes
2
answers
159
views
4D Duoprisms based on nonconvex polygons
A duoprism is a polytope
that can be expressed as the Cartesian product of two polytopes (each of dimension $\ge 2$).
Four-dimensional duoprisms in particular have been studied:
$$P \times Q = \{ (...
10
votes
1
answer
799
views
Triangulations of polytopes and tilings of zonotopes
Consider a set $A = \{ a_1,a_2,\ldots, a_n \} $ of vectors in $\mathbb{R}^d$, which lie in a common affine hyperplane. Two convex polytopes may be obtained from $A$, namely the convex hull of the ...
17
votes
0
answers
361
views
Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?
Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation
it stays a convex polytope,
it stays a combinatorial dodecahedron (i.e. its ...
7
votes
0
answers
161
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 \...
7
votes
1
answer
182
views
In a set of n points on $R^d$, each point can be "well separated" from the rest by a linear functional. Is the dimension necessarily $\Omega(n)$?
For $x\in\mathbb{R}^d$ and $A\subset\mathbb{R}^d$, we say that $x$ is well separated from $A$ if there is a linear functional $f:\mathbb{R}^d\rightarrow\mathbb{R}$ such that $f(A)\subseteq [0,1]$ and $...
1
vote
0
answers
101
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 ...
10
votes
2
answers
655
views
Status of Barany's conjecture?
One of Barany's most intriguing conjectures is about the $f$-vectors of convex polytopes. It asks:
Let $P$ be a convex $d$-polytope. Is it always true that $f_k \geq \min(f_0, f_{d-1})$?
A convex $...
1
vote
0
answers
87
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))$...