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

Filter by
Sorted by
Tagged with
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))$...

1
2
3 4 5
19