# Tagged Questions

**2**

votes

**2**answers

194 views

### Is there a simple test to determine whether a polytope is integral?

It is known that any rational convex polytope expressed as $\{ x\in\mathbb{R}^d : Ax \ge b \}$, where $A\in\mathbb{Z}^{k\times d}$ and $b\in\mathbb{Z}^k$, can be written as the convex hull of finitely ...

**1**

vote

**0**answers

157 views

### Compute generalized pentagram map

Hi,
(This is my first question on MathOverflow! :-)
Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", ...

**8**

votes

**2**answers

372 views

### symmetries and faces of the associahedra

The dihedral group of order $2n+2$ acts on $K_n$, the $n-2$-dimensional associahedron. Are there any other symmetries? References?
Does the answer to 1 change if we restrict to just the 1-skeleton ...

**3**

votes

**3**answers

416 views

### reference for the cubical structure of the associahedra

I cannot find where I learned that the $n$-dimensional associahedron is a union of $n$-cubes. The vertices of the $n$-dimensional associahedron are the finite binary trees having $n+2$ leaves and ...

**9**

votes

**1**answer

676 views

### Approximating a convex function by a piecewise linear function

Suppose I have a Lipschitz-continuous convex function $f:\mathbb{R}^n\rightarrow \mathbb{R}$. I wish to approximate it on the unit ball by a piecewise-linear function $g:\mathbb{R}^n\rightarrow ...

**3**

votes

**1**answer

231 views

### Empty convex polytopes for random point sets

I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane
(the Happy-Ending Problem), and I know that there are higher-dimensional extensions.
A great source ...

**4**

votes

**2**answers

308 views

### Realization spaces for regular convex polytopes

Q1.
Are there convex polytopes combinatorially equivalent to each of the regular polytopes
that are realized with integer vertex coordinates?
...

**11**

votes

**1**answer

371 views

### Can all convex polytopes be realized with vertices on surface of convex body?

The following question was asked by me on Mathematics.SE. Unfortunately, no one answered it so I thought I might give it a try one level higher. Below the line you can find the slightly edited ...

**1**

vote

**2**answers

509 views

### Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph?

A corollary of Euler's formula tells us that the edge-vertex graph of every convex 3-polyhedron must have a face with either 3, 4, or 5 edges, using an argument about the average degree of vertices.
...

**19**

votes

**4**answers

645 views

### Do random projections (approximately) preserve convexity?

The Johnson-Lindenstrauss lemma implies that any set of $k$ points in $\mathbb{R}^d$ can be randomly projected into $d' \approx \log(k)/\epsilon^2$ dimensions such that the distances between each pair ...

**1**

vote

**1**answer

365 views

### Question regard checking convexity by “restriction to any line that intersects the function domain”

Hello all,
I have a question (probably stupid one) about the fact that " A function is convex if and only if it is convex when restricted to any line that intersects its domain".
In Stephen Boyd and ...

**0**

votes

**0**answers

105 views

### Area of spherical polygons in high dimensions

Given 4 points on $S^3$. If we look at the spherical polygon formed on $S^3$, is there a formula for the 3-dimensional Hausdorff measure for it?
E.g.: When I tried to set up a spherical coordinate ...

**2**

votes

**1**answer

458 views

### Proving that a specific function is quasiconvex

Hello all,
Assume we have a sequence of quasiconcave functions (in $X$) denoted by $f_{i,j}(X)$ for $i,j = 1,\ldots,n$. Denote by $F(X)$ the $n\times n$ matrix whose $(i,j)$ entry is the function ...

**5**

votes

**0**answers

95 views

### Regularity of simplices, part deux

This question is directly inspired by Pietro Majer's question and my answer to it.
One can define a simplex, and the dihedral angles thereof in an infinite dimensional Hilbert space (one has to take ...

**4**

votes

**1**answer

181 views

### Regularity of simplices

A triangle is regular, provided it is equilateral, or, also, equiangular. How these conditions generalize to characterizations of regularity of simplices?
In particular, it turns out that
a ...

**1**

vote

**1**answer

182 views

### Realizing not-quite-barycentric subdivision of a polytope

Given a poset $S$, one can form a new poset $I(S)$ whose elements are intervals in $S$ (i.e. either $\emptyset$ or $[a,b]$ for some $a\leq b\in S$) with ordering by (set) inclusion. If $S$ is ranked, ...

**4**

votes

**1**answer

757 views

### Complexity of convex polytope volume calculation ? (Volume of Voronoi cell) (Error probability)

Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i).
I guess complexity of its volume calculate is higher than linear in "N", am I right ?
(Is the complexity ...

**3**

votes

**0**answers

86 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

**2**answers

295 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

**4**answers

724 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

**2**answers

168 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 (identitfying $H$ with $R^4$).
The binary tetrahedral group lies at the vertices of the ...

**2**

votes

**1**answer

149 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

**4**answers

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

**1**answer

379 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

**1**answer

248 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

**1**answer

271 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

**3**answers

264 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

**1**answer

478 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

**2**answers

479 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

**1**answer

183 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

**0**answers

90 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
...

**19**

votes

**1**answer

439 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

**1**answer

401 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

**2**answers

566 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

**1**answer

253 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

**0**answers

250 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

**2**answers

288 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

**0**answers

236 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}( ...

**3**

votes

**3**answers

282 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 ...

**6**

votes

**2**answers

685 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

**1**answer

210 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. ...

**28**

votes

**2**answers

921 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

**2**answers

216 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

**2**answers

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

**2**answers

342 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

**1**answer

264 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

**0**answers

152 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

**2**answers

418 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

**0**answers

145 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
$ ...

**8**

votes

**2**answers

466 views

### When does every point in 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 simplex lies on a chord between two non-adjacent edges of the simplex. Or, ...