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
1answer
75 views

Pictures of the von Neumann polytope

Are there any graphic portrayals of von Neumann polytopes in low dimensions?
11
votes
0answers
99 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
32 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
116 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
47 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
94 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
85 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?
2
votes
1answer
61 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
147 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
67 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
202 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
47 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
0answers
171 views

Number of faces of a polytopal subdivision

Let $\mathcal{P}$ be a (bounded) polytope in $\mathbb{R}^d$ and let $\mathcal{C}$ be a polytopal subdivision of $\mathcal{P}$ [1]. Is there a known tight upper bound in the number of polytopes in ...
1
vote
2answers
98 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
126 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
44 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
108 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
303 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
0answers
71 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
140 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
42 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
452 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
75 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
146 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
51 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 ...
7
votes
1answer
179 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
344 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
108 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
93 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
262 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 ...
1
vote
1answer
126 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 ...
16
votes
0answers
212 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 ...
4
votes
0answers
65 views

How many facets can $\{\|D^T x\|_1\leq 1\}$ have?

$\newcommand{\RR}{\mathbb{R}}$Consider $x\in\RR^n$ and $D\in \RR^{n\times p}$ with $p\geq n$ and full rank. My question is: How many facets can the polytope $ \{x\in\RR^n\ :\ \|D^T x\|_1\leq 1\}$ ...
3
votes
0answers
103 views

Triangulations of special polyhedra

Let $A_1,A_2,A_3 \in \mathbb{N}^3$ be three points in space all lying in some plane $x+y+z=d$ where $d$ is a positive integer. If $\{e_1,e_2,e_3\}$ is the standard basis in $\mathbb{R}^3$, we can ...
2
votes
1answer
131 views

Looking for a canonical (matroid polytope) subdivision of the hypersimplex

A matroid polytope is the convex hull of the indicator vectors of the bases of a matroid, and a matroid polytope subdivision (MPS) is a polyhedral subdivision of a matroid polytope whose cells are ...
0
votes
0answers
76 views

additive support functions of a convex set

Let $K \subset \mathbb{R}^d$ be a compact, convex set. It could be uniquely determined by its support function (for $u$ on the unit-sphere $S^{d-1}$), given by $$h_K(u) = \sup \{ \sum_{i=1}^d x_i ...
21
votes
4answers
571 views

Is the diameter of a centrally symmetric convex body realized by a pair of antipodal points?

Let $S \subset \mathbb{R}^n$ be the boundary of a centrally symmetric convex body and provide $S$ with the geodesic metric given by its embedding in Euclidean space (i.e., the distance between two ...
3
votes
0answers
132 views

Dead Flies Problem [duplicate]

If a set of points in the plane contains one point in each convex region of area 1, then can it have finite density? what is the density of the points? In my understanding, it means the average ...
4
votes
1answer
137 views

Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
5
votes
0answers
105 views

Geometry of the metric cone

Let us say that two metrics $d$ and $d_0$ on a set $X$ are related if there exist positive constants $0 < \alpha \leq \beta$ such that $$ \alpha \,\left(d_0(x,y) + d_0(y,z) - d_0(x,z)\right) \leq ...
0
votes
0answers
91 views

Ref request: If an affine subspace $V$ of $\mathbb R^n$ meets an $n$-dimensional polytope $P$, then it meets $P$ in a face of dimension $\le n-\dim V$

Let $P$ and $V$ be, respectively, a bounded full-dimensional polytope and an $m$-dimensional affine subspace of $\mathbb R^n$, and assume $P \cap V$ is non-empty. Q1. Could you provide me with a ...
2
votes
0answers
61 views

Simplex in convex polytope, pulling triangulation

Let $P$ be a convex $d$-dimensional polytope. I have two questions, related to triangulations of $P$. Question 1: Let $p$ be in the interior of $P$. Can I always find a triangulation of $P$, such ...
3
votes
1answer
69 views

Number of lattice polytopes contained in a given lattice polytope?

Given a (convex) lattice polytope, suppose we want to list or count all (convex) lattice polytopes (of the same dimension) contained in it. Are there efficient ways to do this?
4
votes
0answers
120 views

Regular cross-sections of a dodecahedron; analogous sections of 4-polytopes

One can intersect a dodecahedron with a plane and obtain an equilateral triangle, a square, a regular pentagon, a regular hexagon, and a regular decagon:             ...
1
vote
1answer
72 views

What is the functional form of the projections of a subdimensional polytope?

Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation: ...
3
votes
1answer
105 views

On a conjecture by Hibi regarding h-vectors

For integral polytopes, it is conjectured (T. Hibi), that if the $h^*$-vector is symmetric, then it is also unimodal (increasing, then non-decreasing). A non-integral polytope do not, in general, ...
6
votes
0answers
119 views

Sampling from a Convex Body with Many Extremal Points

Let $p_{1}, \ldots, p_{N}$ be a collection of points in $\mathbb{R}^{n}$. I would like to sample uniformly from the convex hull of these $N$ points in an `efficienct' way. In my setting, I have $n$ ...
1
vote
0answers
63 views

Stronger condition than being a normal polytope?

A polytope $P$ with integer vertices is called normal if for every $p = \sum_j a_j p_j $ such that $a_j \geq 0$, $\sum_j a_j = k \in \mathbb{N}$, $p_j$ are vertices of $P$ and $p$ is an integer ...
2
votes
1answer
56 views

The minimal number of halfspaces to represent a convex but non strongly convex cone

We say a cone at the origin in $R^n$ means that it is an intersection of finitely many halfspaces, i.e. $$C=\bigcap_{i\in I}H_i,\text{ where }|I|<\infty.$$ A cone is strongly convex if $C\cap ...
6
votes
0answers
130 views

An affine invariant of convex bodies

The following invariants of "pointed" convex bodies (i.e., pairs consisting of a convex body and a distinguished point in its interior) roughly measure how many of its linear images fit between the ...