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
3
votes
1answer
29 views
Which unfoldings of the hypercube tile 3-space: How to check for isometric space-fillers?
Recently Mark McClure constructed and displayed
the 261 unfoldings of the hypercube (tesseract)
in response to the question,
"3D models of the unfoldings of the hypercube?":
The first 9 unfoldings ...
3
votes
2answers
89 views
regular polyhedra (and polytopes) in hyperbolic geometry, and generalisations
While there exist regular tesselations of the hyperbolic plane with arbitrary regular polygons, there are no new regular polyhedra in hyperbolic (3D) space. This being quite trivial, it is probably ...
4
votes
0answers
63 views
Approximation of convex body by polytopes
In a recent survey paper, Approximation of convex sets by polytopes, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$,
$$\rho_H(U,\mathcal{P}_n)\leq c(U) ...
4
votes
0answers
50 views
Can the GUE be thought of as a uniform point in a high-dimensional polytope
I have thought about this question for a long time and could only find partial answers.
The Gaussian Unitary Ensemble (or GUE) is the eigenvalues of a random Hermitian matrix with complex Gaussian ...
8
votes
1answer
197 views
3D models of the unfoldings of the hypercube?
There are (apparently) 261 distinct unfoldings of the 4D hypercube, a.k.a., the
tesseract, into 3D.1
These unfoldings (or "nets") are analogous to the 11 unfoldings of
the 3D cube into the plane.2
...
3
votes
0answers
42 views
max volume of inscribed simplex in a ball
Let $B_n$ be the $n$-dimensional unit ball, and $B_n(\epsilon)$ be the spherical cap with height $\epsilon$ I am interested in the quantity
$$\Gamma:=\sup_{\Delta:\textrm{ inscribed simplex in ...
1
vote
0answers
39 views
Conditions on probability measure that generates non-void random polytope
Let $C$ be a non-void compact convex set in $\mathbb{R}^d$, and $\nu$ a probability measure on $C$. Then under what conditions on $C$ and $\nu$, the following statement is true: If ...
6
votes
1answer
70 views
two-dimensional sections of polyhedral cones
Given a polyhedral cone, its intersection with any two-dimensional plane is either a polygon or a region enclosed by a polygonal curve. Is it a characterization of polyhedral cones? Does there exists ...
4
votes
0answers
53 views
Is every planar point set be projections of vertices of a neighborly 4-polytope?
More exactly, written in coordinates, I'm curious to know if for every point set $(x_i,y_i)$ there are $(x_i,y_i,z_i,w_i)$ be vertices of a neighborly polytope.
This problem comes from a simple ...
3
votes
0answers
108 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 ...
1
vote
1answer
60 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
83 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
41 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 ...
0
votes
0answers
40 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 ...
5
votes
1answer
304 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 ...
12
votes
4answers
467 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 ...
5
votes
1answer
147 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
169 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
230 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 ...
2
votes
0answers
163 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
28 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
89 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
284 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 ...
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 ...
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 ...
1
vote
1answer
132 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
71 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$, ...
5
votes
2answers
147 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
61 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
427 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
333 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
73 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
261 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
72 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
187 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
183 views
Pictures of the von Neumann polytope
Are there any graphic portrayals of von Neumann polytopes in low dimensions?
15
votes
1answer
237 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
45 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
130 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
54 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
135 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
99 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
87 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
158 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
78 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
218 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
73 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
127 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
142 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$ ...
