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

5
votes
1answer
164 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 ...
7
votes
1answer
175 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 ...
4
votes
2answers
239 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 ...
3
votes
1answer
195 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 ...
0
votes
0answers
32 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
137 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 ...
10
votes
1answer
298 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 ...
43
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 ...
12
votes
0answers
164 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 ...
1
vote
1answer
176 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, ...
7
votes
0answers
82 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$, ...
8
votes
3answers
356 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 ...
1
vote
0answers
74 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 ...
14
votes
4answers
449 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 ...
7
votes
2answers
370 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 ...
3
votes
1answer
77 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
279 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 ...
0
votes
2answers
79 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
192 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 ...
6
votes
2answers
190 views

Pictures of the von Neumann polytope

Are there any graphic portrayals of von Neumann polytopes in low dimensions?
15
votes
1answer
268 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
46 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 ...
1
vote
1answer
140 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 ...
3
votes
0answers
55 views

Polynomials connected with Gale's condition and cyclic polytopes

I was reading about cyclic polytopes and (I think naturally) became interested in polynomials $f(X) \in \mathbb{R}[X]$ which have a factorization of the form $f(X)=g(X)g(X+1)$ for some $g(X) \in ...
3
votes
1answer
164 views

$\mathcal{H}$-polyhedron under a linear map

Let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a (bounded) polyhedron for $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, $n,m > 0$. Moreover, let $M \colon \mathbb{R}^n \to ...
2
votes
1answer
100 views

Criteria for abstract polytopes to be convex polytope

Suppose I have an abstract polytope defined by a poset. Are there any methods for determining whether the abstract polytope can be geometrically realized as convex-hull on its set of vertices?
3
votes
2answers
131 views

How to (efficiently) find intersection of two polyhedral cones?

I have two polyhedral cones represented by their rays. I am looking to find their intersection, which would also be a polyhedral cone, hopefully efficiently. Does anybody know a way to do that? ...
4
votes
2answers
169 views

Build a topological polytope with a specified CW-structure

I am a topologist and not quite familiar with the tools for building a polytope. I would like to build some topological polytope which is an somewhere in between permutohedron and associahedron which ...
1
vote
0answers
84 views

Convex Optimization related problem

Suppose two non-negative convex functions $f$ and $g$ be given. We want to solve the following optimization $$\max_{g\leq\epsilon}f.$$ Now suppose that both $f$ and $g$ can be upper-bounded by a ...
5
votes
2answers
235 views

Are shortest halving curves simple closed geodesics?

Let $S$ be a smooth convex surface in $\mathbb{R}^3$ (although my question may as well be asked for the surface of a polyhedron). Say that $\gamma$ is a shortest halving curve if (a) it partitions the ...
2
votes
0answers
79 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 ...
1
vote
2answers
158 views

Volume of normal cone of a simplex (at a vertex)

This question is related to an orthant-type simplex in $\mathbb{R}^n$, which can be defined as $$ S = \{x\in\mathbb{R}_{+}^n: \sum_{i=1}^nx_i \leq 1\}=\overline{\mbox{conv}}(0,e_1,\ldots,e_n). $$ For ...
2
votes
1answer
161 views

intersection of the unit cube and a hyperplane containing the main diagonal

Let $A$ be a linear $m$-dimensional subspace of $\mathbf{R}^n$ $m < n$, containing the point $(1,1,\ldots,1) \in \mathbf{R}^n$, and consider the intersection of $A$ and the unit cube $\Delta_n$ ...
3
votes
0answers
47 views

Minimax-like theorems involving union and intersection of regions in $\mathbb R^d$

From Minimax theorems, we roughly know that if $f(x,y)$ is convex on $X$ and concave $Y$ for both compact $X,Y$, then: $$ \max_{x\in X}\min_{y\in Y} f(x,y)=\min_{y\in Y}\max_{x\in X} f(x,y). $$ We can ...
4
votes
1answer
146 views

The number of facets of a polyhedron under linear transformation

Consider a (not necessarily bounded) convex polyhedron $P\subset \mathbb{R}^n$ which has $k$ facets. Let $L:\mathbb{R}^n \to \mathbb{R}^m$ be a linear transformation. Question1: Is there a fixed ...
5
votes
1answer
529 views

Linear transformation of a polyhedron

Is there a simple proof that shows: Linear transformation of a $\mathcal{H}$-polyhedron (i.e. the intersection of finitely many closed half-spaces) is a $\mathcal{H}$-polyhedron. Minkowski sum of ...
3
votes
2answers
156 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 ...
2
votes
1answer
153 views

Vertices of a polytope as algebra generators

I am wondering if the following kind of objects has some name, or are there any studied examples. I apologize for perhaps too specific definition, this is an adoptation of a situation that arises in ...
0
votes
0answers
54 views

Paths on Cartesian products of graphs satisfying linear constraints

Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ ...
21
votes
2answers
501 views

Convex hull of total orders

Let $n$ be a positive integer and $\prec$ an arbitray total order on $\{1,\dots,n\}$. I associate to this order a vector $v$ with one coordinate for every pair $(i,j)$ s.t. $1\leq i\neq j \leq n$, by ...
2
votes
1answer
84 views

Volume of a polytope with relaxed constraints

Consider a polytope in $n$ dimensions defined by a set of linear constraints: $$P = \{x \in \mathbb{R}^n : Ax \leq b\}$$ where A is some $m \times n$ constraint matrix, and $b = (b_1,\ldots,b_m)$ is ...
2
votes
0answers
223 views

Cavalieri's principle and inversion of the Vandermonde matrix

There are many examples on the Web of the use of Cavalieri's principle in determining areas and volumes of 2-D and 3-D geometrical figures. The Wikipedia link uses the principle as both a proof and ...
1
vote
0answers
59 views

Does the set of points minimizing their distance to a multiset of convex polytopes result in a polytope?

Let $\mathbb{R}^n$ be a normed affine space of finite dimension $n$, and $d : \mathbb{R}^n \times \mathbb{R}^n \mapsto \mathbb{R}^+$ be the distance derived from the norm under consideration. A convex ...
8
votes
1answer
196 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 ...
13
votes
0answers
347 views

Surface area of convex hull [duplicate]

Let Q be the convex hull of a non-convex polyhedron P. Is it true that the surface area of Q is not greater than the surface area of P?
2
votes
1answer
129 views

The Mahler conjecture and non-zonoidal 3-polytopes (4-polytopes)

I have been working on the Mahler conjecture for over a year now and have made some progress for certain classes of convex polytopes and I'm now attempting to write up my results specified to ...
2
votes
1answer
104 views

Integrally closed polytopes from 01-matrices

Let $A$ be a matrix with entries either 0 or 1, where each column contains at least one 1, to remove trivial degenerations. Let $P$ be the convex hull of all integer vectors $x$ that satisfy $Ax \leq ...
10
votes
1answer
317 views

doubly-stochastic isomorphisms of graphs

A doubly stochastic matrix that commutes with the adjacency matrix of a graph is a doubly-stochastic automorphism of that graph (definition by Tinhofer 1986). Each (classical) automorphism of a graph ...
2
votes
1answer
157 views

Calculate the discrete set of points B which are in the convex hull of the set of points A

This problem is likely best described with the following picture: Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
17
votes
0answers
278 views

“Japanese Theorem” on cyclic polygons: Higher-dimensional generalizations?

A beautiful theorem known as the Japanese Theorem (Wikipedia, MathWorld) says that, no matter how one triangulates a cyclic (inscribed in a circle) polygon, the sum of the radii of the incircles is ...