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

learn more… | top users | synonyms

3
votes
0answers
86 views

Looking for the correct version of a wrong statement from Barvinok's book on convex polyhedra

The book I'm concerned with is "Integer Points in Polyhedra" by A. Barvinok, which, I must say, is turning out to be highly fascinating. A real finite-dimensional vector space $V$ defines the ...
51
votes
2answers
5k 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 ...
18
votes
13answers
3k views

Generalizations of the Birkhoff-von Neumann Theorem

The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices. The question is to point out different ...
5
votes
1answer
277 views

Examples of Polyhedra with Large Shadows

Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
1
vote
1answer
34 views

What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely, $X \in ...
1
vote
1answer
77 views

Is mean width a Dehn invariant?

Let $P \subset \mathbf{R}^3$ be a convex polyhedron. Let $rP$ be the dilation of $P$ by the positive real number $r$. The Dehn invariant of $P$ is an element of the weird real vector space ...
2
votes
1answer
32 views

Sampling point uniformly at random satisfying equality constraints

First of all, I apologize in advance if the question has already been asked in some way on this site and/or if there is a widely known solution to this problem. The description of my problem is ...
0
votes
0answers
20 views

Looking for a homogeneous function with some properties

I'm looking for a 1-homogeneous function $\pi \colon \mathbb{R}^n_{\geq 0} \to \mathbb{R}$ satisfying the following properties: 1) $\pi$ is not concave. This is equivalent to the fact that there ...
7
votes
2answers
672 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 ...
0
votes
0answers
36 views

Number of faces of polytope projecting to lower dimensional polyhedron

Denote $K=\mathrm{conv}(v_1, \ldots, v_n)\subsetneq\Bbb R^m$ to be convex set spanned by vectors $v_i\in\Bbb R^m$ with $m\leq n$ then what technique could be useful to upper bound minimum number of ...
36
votes
0answers
852 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 ...
3
votes
1answer
150 views

n-dimensional Delaunay Triangulation of Lattices

I have several questions concerning the Delaunay triangulation of a high dimensional lattice. Given an $n$-dimensional lattice $L$ and its Delaunay triangulation (partition of $R^n$ into simplices ...
1
vote
1answer
105 views

Regular unimodular triangulation for a certain simplex

Consider an $n$-simplex with vertices given by $(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers, and $i=0,1,\dots,n+1$. Does this simplex admit a regular, ...
4
votes
1answer
209 views

convex polyhedron in the unit cube

Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where ...
7
votes
1answer
166 views

A polytope with a bound on the sum of any $k$ variables

Let $2\le k\le n-1$ and define the polytope $$P_k(n) = \lbrace (x_1,\ldots,x_n) \in \mathbb{R}^n : -1\le x_{i_1}+\cdots +x_{i_k} \le 1 \text{ for all } 1\le i_1\lt\cdots\lt i_k\le n\rbrace.$$ There ...
13
votes
2answers
962 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 ...
42
votes
2answers
2k 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 ...
2
votes
0answers
159 views

Dehn-Sommerville relations for $\Delta$-complexes

Let $M$ be a closed, triangulated manifold of dimension $m$ and $K(M)$ be its triangulation. Let $f_i$ denote the number of $i$-simplices of $K(M)$. As proved by Klee the face numbers satisfy the ...
11
votes
2answers
304 views

What is the number of equitriangulations of the n-cube?

I wonder if this question has been considered before and if anything is known. My search attempts have failed so far. Let's consider the n-dimesnional cube, $[0,1]^n$, and let's call a simplex with ...
4
votes
1answer
133 views

Non-closed geodesics on a convex polyhedron in $\mathbb{R}^3$

Let $P$ be the surface of a closed convex polyhedron in $\mathbb{R}^3$. Q. Does every non-closed geodesic $\gamma$ fill $P$ densely? Of course $\gamma$ cannot pass through a vertex of $P$, but ...
4
votes
2answers
226 views

Marked chain polytope, has this been studied?

Fix $n$ and consider the polytope given by the inequalities $$x_i\leq x_j, \text{ and } 0 \leq x_i \leq a_i \text{ for all } 1\leq i<j \leq n,$$ where $a_i \leq a_i\leq \dots \leq a_n$ are fixed ...
0
votes
0answers
27 views

continuous extensions of concave functions

Let $N$ be a lattice. For a ring R we denote $N_R := N \otimes R$. My question is the following: Does a continuous and concave function \begin{eqnarray*} f: N_{\mathbb{Q}} \to \mathbb{R} ...
1
vote
1answer
86 views

Linear map of Zonotopes [closed]

Consider a linear system with a map $A: \mathbb{R}^n \rightarrow \mathbb{R}^m$ such that $y = A x$ with $n \geq m$ The input space $x$ is constrained by a zonotope set $\mathcal{X} \subseteq ...
9
votes
1answer
364 views

Question about tetrahedron decomposition

Are there tetrahedra which can be subdivided into three non-overlapping parts similar to the original? I believe this would require splitting one face into three parts. I know some types of tetrahedra ...
10
votes
1answer
277 views

What's the volume of $\{x\in[0,1]^n|\sum x_i\le t\}$ for real $t$?

EDIT: Thanks for your answers and comments. There is indeed a classical easy formula, given by Pietro Majer (with a simple nice proof) in his answer below. Given $x\in\mathbb{R}^n$, $x_i$ denotes ...
7
votes
0answers
66 views

What does this number tell me about a convex lattice polygon?

EDIT: I realized I'd tricked myself by working with a too special case of $f$, the question is now updated (boundary lattice points replaced vertices). Suppose I have a convex lattice polygon $P$, ...
10
votes
0answers
119 views

Polytopes with few vertices and few facets

I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...
5
votes
2answers
143 views

Positivity of Ehrhart polynomial coefficients

Are there any results stating that a given family of convex polytopes have Ehrhart polynomials with non-negative coefficients? What methods are available for proving such a property for some family ...
3
votes
3answers
278 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 ...
17
votes
10answers
7k 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 ...
6
votes
2answers
615 views

“MultiCatalan numbers”

Could anyone provide a reference for the following (sort of) generalization of Catalan numbers: the multinomial coefficient $$ \binom{2k_1+3k_2+4k_3+...}{k_1+2k_2+3k_3+...,k_1,k_2,k_3,...} $$ is ...
1
vote
0answers
58 views

Looking for the manuscript “Uniform polytopes” by N. Johnson

The manuscript Uniform Polytopes (1991) by Norman Johnson is cited in the wikipedia page on uniform polytopes (http://en.wikipedia.org/wiki/Uniform_polytope). Is there an electronic copy of this ...
7
votes
2answers
321 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 ...
14
votes
4answers
418 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 ...
2
votes
0answers
71 views

Generators for lattice polytopes

Let $V$ be a finite set of integral vectors in $\mathbb{R}^n$. Consider the real (positive) convex cone $\mathbb{R}_+V$ spanned by $V$. We can assume that all vectors in $V$ are extremal in ...
5
votes
5answers
1k views

coordinates of vertices of regular simplex

For $d=3$, vertex coordinates of a regular simplex have a simple expression since vertices correspond to four vertices of a cube. Is there a simple expression for higher dimensions? In particular I'm ...
3
votes
1answer
71 views

Are all marked order polytopes normal?

Richard Stanley showed that order polytopes have a unimodlar ttriangulation. In particular, this implies that they are integrally closed/normal. One can generalize order polytopes to marked order ...
4
votes
2answers
249 views

Convex Sets and Nearest Neighbors

For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is uniquely determined. It is known that ...
3
votes
1answer
347 views

Convex n-polytope general position vectors to general position vectors of tetrahedron

I asked this question in a comment to this question, but got no response. I thought that perhaps it needed more exposure, so I made it a question in itself. Define a set of general position vectors ...
16
votes
1answer
397 views

Egalitarian measures

A question I got asked I while ago: If $T$ is a triangle in $\mathbb R^2$, is there a function $f:T\to\mathbb R$ such that the integral of $f$ over each straight segment connecting two points in the ...
0
votes
2answers
68 views

Information needed to distinguish combinatorially isomorphic polytopes (up to affine equivalence)

I originally posted this question on Stack Exchange, thinking it perhaps does not qualify as "research-level" but it received no answers... hopefully someone here can help. The title pretty much ...
6
votes
1answer
183 views

Some polytopes in $\mathbb R^n$ whose vertices have coordinates 1, -1 or 0

Let $n$ and $k$ be positive integers with $k\leq n$. Let $P(n,k)$ be the convex hull in $\mathbb R^n$ of the $2^k {n \choose k}$ vectors whose exactly $k$ coordinates belong to $\{\pm 1\}$ all the ...
3
votes
2answers
125 views

Unimodular triangulation and Ehrhart polynomials

Let $P$ be a convex lattice polytope. Then it has a polynomial Ehrhart function. I am interested in what can be said about the Ehrhart polynomial when $P$ has any of the properties is integrally ...
1
vote
2answers
1k 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 (...
10
votes
1answer
1k views

Characterizing faces of 3-dimensional polyhedra. (Related to Victor Eberhard's Theorem [1890]:)

Originally asked by Ali Dino Jumani; EXTENSIVELY EDITED by David Speyer. The previous version was a bit confused, but Steven Sivek and Graham, in the comments, figured out what was going on. G. C. ...
6
votes
2answers
183 views

Pictures of the von Neumann polytope

Are there any graphic portrayals of von Neumann polytopes in low dimensions?
15
votes
1answer
232 views

Higher dimensional generalization of: Any quadrilateral tiles the plane?

Any (non-self-intersecting) quadrilateral tiles the plane.     (MathWorld image.) Q. What is the strongest known generalization of this statement to higher dimensions? I.e., ...
0
votes
0answers
44 views

construction of four dimensional regular convex polytopes

Could anybody give me a reference book about the explicit construction of the 6 regular four dimensional convex polytopes. I cannot easily find Schläfli's original paper so I am looking for a modern ...
12
votes
1answer
640 views

Optimal 8-vertex isoperimetric polyhedron?

I know from Marcel Berger's Geometry Revealed: A Jacob's Ladder to Modern Higher Geometry (p.531) that it is not yet established which polyhedron in $\mathbb{R}^3$ on 8 vertices achieves the optimal ...
1
vote
1answer
127 views

Estimating the volume of a union of balls

Let $\{ B_i \}_{i=1}^n$ be a set of $n$ ball in the unit cube $C$ of dimension $d$. If I want to estimate $$ \frac{ \lambda \left( \cup B_i \right) }{\lambda\left( C \right) }, \tag{1} $$ where ...