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
85 views

Versions of Helly's Theorem for Unbounded Parallelpipeds

I'm studying Frobenius splitting of toric varieties based on Sam Payne's characterization of Frobenius splitting ("Frobenius splittings of toric varieties" (2008)) and I came across a sort of Helly's ...
3
votes
2answers
283 views

How to show that convex polytope is not a Voronoi cell?

Given a combinatorial type of a convex polytope, what techniques are available for showing that it cannot be realized as a Voronoi cell of some point system?
17
votes
4answers
675 views

The Constructions of Davis and Januszkiewicz

One of the most useful tools in the study of convex polytope is to move from polytopes (through their fans) to toric varieties and see how properties of the associated toric variety reflects back on ...
2
votes
1answer
141 views

How can pushing a vertex in a polytope lead to merging facets?

I'm trying to understand the Lemma 2.2 and Corollary 2.3 of Francisco Santos paper "A counterexample to the Hirsch conjecture": http://arxiv.org/abs/1006.2814 Corollary 2.3 is a proof of a result of ...
27
votes
4answers
1k views

Probability of zero in a random matrix

Let $M(n,k)$ be the set of $n\times n$ matrices of nonnegative integers such that every row and every column sums to $k$. Let $P(n,k)$ be the fraction of such matrices which have no zero entries, ...
0
votes
1answer
334 views

The query concerning the Euler-Poincare formula’s generalizations

Euler's equation for polyhedral, Euler's polyhedral formula, V – E + F = 2, where V, E, and F, are the number of points, edges and faces, was discovered by Leonhard Euler in 1752. However, the basic ...
4
votes
1answer
223 views

Is it possible to sample uniformly on the surface of a high-dimensional polytope?

There are some pretty simple methods to do uniform sampling on the surface of high-dimensional spheres or cubes. Are there any methods that sample uniformly on the surface of a high-dimensional ...
10
votes
1answer
254 views

Connecting Lemma in the Alexandrov's existence theorem.

At the moment I am polishing my lecture notes which in particular cover Alexandrov's existence theorem. Denote by $\mathbf{P}_k$ the space of isometry classes of polyhedral metrics on the $\mathbb ...
6
votes
3answers
259 views

Inequality of arithmetic and geometric means for the lattice polytopes?

Let $K$,$L$,$M$ be convex lattice polytopes (so their vertices are in $\mathbb{Z}^n$) in $\mathbb{R}^n$ satisfying $K+L\subseteq M+M$ (Minkowski sum). Do we always have ...
8
votes
1answer
434 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 ...
9
votes
2answers
459 views

Detecting tilings by toric geometry

This is probably a silly question, but I figured that if there is a good answer, this would be a good place to ask. Ever since I got my hands on the book "Toric Varieties" by Cox, Little and Schenck, ...
3
votes
1answer
181 views

The facial structure of the convex hull of a family of characteristic functions

Let $S$ be a finite set and let $\mathcal{A} \subset\mathcal{P}(S)$ be a family of subsets of $S$. Consider the convex polytope spanned by the characteristic functions of members of $\mathcal{A}$ : ...
0
votes
0answers
83 views

centrally symmetric neighborly polytopes.

Let $P$ is centrally symmetric $k$ neighborly d-polytope. Let $ P^* $ is polar( also dual) of $ P $. Consider a polytope $ Q^* $ , $ Q^* \subset P^* $( not necessarily a face of $P^*$). By duality ...
10
votes
0answers
264 views

Update to Shephard's “Twenty Problems on Convex Polyhedra”

Forty-three years ago, Geoffrey Shephard published an influential list of open problems on convex polyhedra. Progress has been made on several of his problems, and perhaps some have been completely ...
2
votes
1answer
367 views

faces of a polytope

Let $a_1,a_2,..,a_n\in\mathbb{R}^m$, $n>m$ and the points are in general position meaning, no hyperplane contains more than $m$ points. Define a polyhedron $$P=\{x\in\mathbb{R}^m:a_1'x\leq0, ...
2
votes
2answers
532 views

Cone over the Join of two topological spaces

Suppose $X$ and $Y$ are topological spaces. Let's define the join $X\ast Y$ as the quotient space $X\times Y\times [0,1]/\sim$, where $\sim$ is the equivalence relation generated by ...
2
votes
1answer
244 views

Max/min problems related to associahedra or their duals (ions on balls revisited)

Original motivation: This is a follow-up question to and generalization of MO Q78877 on equilibrium configurations of ions on n-Dim balls. Henry Cohn gave an excellent answer dispelling my naive ...
2
votes
0answers
221 views

Minimum solid angle and aspect ratio of an $n$-simplex

In computational geometry and other fields, it is of interest to have degeneracy measures for shapes of simplices, which quantitatively seperate the regular simplex from degenerate simplices. In two ...
2
votes
2answers
256 views

Bound on the (anticanonical) degree of toric Fano varieties

Does there exists a universal constant $C \geq 1$ such that if $X$ is any a smooth, toric, Fano $n$-dimensional manifold admitting a Kähler-Einstein metric, then its anticanonical degree $(-K_X)^n$ ...
3
votes
0answers
232 views

Place n telescopes on a sphere in R^d to see the whole sky

Where would one put $n$ telescopes on the surface of the earth to see the whole sky as well as possible ? Use the cosine metric to define how well we can see in direction $x$: $ \qquad \text{cansee}( ...
2
votes
2answers
238 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 ...
5
votes
2answers
523 views

Finding the convex combination of vertices which yields an inner point of a polytope

Given a convex polytope $P\in \mathbb{R}^n$, and a point $x\in P$, Caratheodory's theorem gives us that there exists a set of at most $n+1$ vertices of $P$, such that $x$ is a convex combination of ...
3
votes
1answer
207 views

Is the number of vertices of a convex $d-$dimensional lattice polytop without interior lattice points bounded?

The lattice polytop $[0,n_1]\times[0,n_2]\times\dots\times[0,n_{d-1}]\times[0,1]$ contains $(n_1+1)(n_2+1)\cdots(n_{d-1}+1)2$ integral points on the boundary and no integral points in its interior. ...
26
votes
2answers
853 views

Bodies of constant width?

In two-dimensional case one can generalize figures of constant width as figures which can rotate in a covex polygon. Here is one example which can be used to drill triangular holes: I would like to ...
6
votes
2answers
213 views

convex polytopes with many faces and edges but few cells and vertices

For a convex polytope $P$ in $\mathbb R^4$, denote by $N_0,N_1,N_2,N_3$ respectively the number of vertices, edges, faces, cells. By Euler's formula, we know $N_0+N_2=N_1+N_3$, which means there is a ...
13
votes
2answers
1k 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
2answers
304 views

Does an $n$ dimensional subspace intersect the $n$-facets of the unit cube?

Since my intuition for high dimensional geometry is not always right: Consider the unit cube in $\mathbb{R}^m$ and for $n\leq m$ denote by $F^n$ the union of the $n$-facets. For what numbers of $m$ ...
1
vote
1answer
248 views

Hypercube vertex sampling with largest convex cone

Maybe this question was already asked and forgive me if I can't formulate it well. Lets assume we have a n-dimensional hypercube. If we want the smallest set of vertices such that the cube is inside ...
1
vote
0answers
137 views

When is the conical hull of a finite set of vectors a subset of the space? (and tilings)

Consider a hypercube in n-dimensions, and take some projection down to an m-dimensional subspace. Now take all vertices and m-1 dimensional facets visible from some direction outside the projection. ...
5
votes
2answers
346 views

Measure of intersection of polyhedral cone with unit sphere

Let $C$ be a pointed polyhedral cone in $\mathbb{R}^n$ and let $S^{n-1}$ denote the unit sphere in $\mathbb{R}^n$. Given a description of the supporting hyperplanes of $C$ is there an algorithm for ...
3
votes
0answers
143 views

An isoperimetric inequality for “order” polytopes

I am looking for an isoperimetric inequality for order-like polytopes. An order polytope $K\in \mathbb{R}^n$ is defined by a set of linear inequaities: $$ \forall i \; 0\leq x_i \leq 1 $$ and $ ...
7
votes
2answers
427 views

When does every point in the volume of a polytope lie along a chord between its edges?

Consider the 3-simplex, or tetrahedron, in 3-space. Regardless of the positions of the vertices, every point in the volume defined by the triangular faces of the polytope's skeleton graph can lie ...
8
votes
1answer
1k views

About the surface area vs. volume of polytopes

Given a convex body $K\in\mathbb{R}^n$, represented by a set of linear inequalities (intersection of halfspaces), I am interested in understanding how much of its volume can be close to its perimeter ...
11
votes
2answers
2k views

Weighted area of a Voronoi cell

Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
17
votes
0answers
2k views

Why do polytopes pop up in Lagrange inversion?

I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
5
votes
1answer
324 views

Isometric embedding a convex cap to render its boundary planar

I would like to know if there is a polyhedral analog to this beautiful theorem of Hong: Theorem 11.0.1. Any smooth positive disk $(\bar{D},g)$ with a positive geodesic curvature along ...
0
votes
0answers
324 views

Upper and Lower Bounds of the Total Surface Area of Convex Polytopes that Partition a Hypercube

Let $C$ be a hypercube in $\mathbb{R}^D$ with edge length of $L$. Let $\mathcal{P}_1,\ldots,\mathcal{P}_K$ be $K$ convex polytopes that partition $C$. Let $S_k$ be the surface area of the polytope ...
5
votes
3answers
1k views

Random Sampling a linearly constrained region in n-dimensions…

Hi, So here is my problem: Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$ $x_n \le c_n$ and $\sum_{n=1}^N x_n = 1$ find an ...
2
votes
0answers
202 views

Sampling from a partition of a hypercube by convex polytopes.

I have a binary space partitioning (BSP) tree which recursively partitions a hypercube using linear hyperplanes. That is, a hyperplane splits the hybercube in half, creating two convex polytopes. Each ...
1
vote
2answers
423 views

Extreme points of transportation polytope

I'm interested in $n \times m$ joint probability tables with prescribed row and column marginals. Such tables form a convex set known as the transportation polytope. What are the extreme points of ...
2
votes
2answers
472 views

Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center

Does this already exist in literature? The closest Ive been able to find is circumscribe intersection of two ellipsoids with a common center by W. Kahan ...
2
votes
1answer
281 views

Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample

Definitions Let $\mathcal{C}$ be a convex polytope in $\mathbb{R}^{D}$ with $K$-facets $F_{1},\ldots,F_{K}$. I denote the normal vector of the $k^\mathrm{th}$ facet as ...
7
votes
3answers
625 views

Not quite regular polyhedra

Take a naive interpretation of regular polyhedra: All vertices (including epsilon ball) congruent All edges congruent All faces congruent We can now find interesting families by removing one ...
9
votes
3answers
714 views

Polytopes with few vertices.

Suppose I have a convex polytope in $\mathbb{R}^d$ which I know has few vertices (in the case which prompted this question, I seem to have a polytope in $\mathbb{R}^9$ which has sixteen vertices). Is ...
5
votes
1answer
297 views

Recovering a polyhedron from its tumble-density profile

Imagine a white convex polyhedron $P$ tumbling randomly about its fixed center of gravity (c.g.) $c$ against a blue background. A long-exposure photo would show pure white in a neighborhood of $c$ ...
8
votes
1answer
581 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 ...
13
votes
2answers
681 views

Sampling from the Birkhoff polytope

The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope Recently someone asked me if I knew How to sample (in polynomial time) ...
7
votes
2answers
653 views

Regular polygon shadows of convex polyhedra

Fix a finite subset $S$ of the natural numbers $\mathbb{N}$, each element $\ge 3$. Is there a convex polyhedron $P$ that has among its shadows regular $n$-gons for each $n \in S$? Does such a ...
1
vote
1answer
207 views

Representing integer points inside a polytope using a unit hypercube

Let $D\subset\mathbb{Z}\times\mathbb{Z}$ such that $D$ is formed by the points bounded by a convex polytope. Let $f:D\to\mathbb{R}$ defined by $f(x,y)=ax+by+c$, where $a,b,c\in\mathbb{R}$ and ...
14
votes
1answer
572 views

Totally rational polytopes

Define a convex polytope in $\mathbb{R}^d$ as totally rational (my terminology) if its vertex coordinates are rational, its edge lengths are rational, its two-dimensional face areas are rational, ...