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

56
votes
2answers
6k views

The amplituhedron minus the physics

Is it possible to appreciate the geometric/polytopal properties of the amplituhedron without delving into the physics that gave rise to it? All the descriptions I've so far encountered assume ...
48
votes
5answers
2k views

Do unit quaternions at vertices of a regular 4-simplex, one being 1, generate a free group?

Choose unit quaternions $q_0, q_1, q_2, q_3, q_4$ that form the vertices of a regular 4-simplex in the quaternions. Assume $q_0 = 1$. Let the other four generate a group via quaternion ...
46
votes
8answers
7k views

Fair but irregular polyhedral dice

I am interested in determining a collection of geometric conditions that will guarantee that a convex polyhedron of $n$ faces is a fair die in the sense that, upon random rolling, it has an equal $1/n$...
45
votes
0answers
1k views

Intersecting Family of Triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
44
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 ...
41
votes
1answer
2k views

two tetrahedra in R^4

It is relatively easy to show (see below) that if we have two equilateral triangles of side 1 in $R^3$, such that their union has diameter 1, then they must share a vertex. I wonder whether we have an ...
36
votes
4answers
3k views

Polynomial roots and convexity

A couple of years ago, I came up with the following question, to which I have no answer to this day. I have asked a few people about this, most of my teachers and some friends, but noone had ever ...
34
votes
14answers
8k views

Open problems in Euclidean geometry?

Which are some (research level) open problems in Euclidean geometry ? (Edit: I ask just out of curiosity, to understand how -and if- nowadays this is not a "dead" field yet) I should clarify a bit ...
33
votes
2answers
2k views

Do plane projections determine a convex polytope?

Suppose a compact convex body $P \subset \Bbb R^3$ has only polygonal orthogonal projections onto a plane. Does this imply that $P$ is a convex polytope? This question occurred to me when I was ...
30
votes
0answers
2k views

A Combinatorial Abstraction for The “Polynomial Hirsch Conjecture”

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ . Suppose that (*) For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
29
votes
2answers
977 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 ...
28
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, ...
28
votes
2answers
1k views

The logic of convex sets

Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so ...
24
votes
2answers
565 views

Complete the following sequence: point, triangle, octahedron, . . . in a dg-category

Let $\mathcal C$ be a pre-triangulated dg-category (or a stable $\infty$-category, if you wish). An object $X$ in $\mathcal C$ gives a "point": $$X$$ A morphism $X\xrightarrow f Y$ in $\mathcal C$ ...
23
votes
10answers
11k views

Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
23
votes
2answers
527 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 ...
23
votes
4answers
2k views

Ellipse naturally associated with a polygon

My colleagues and I have stumbled onto a way to associate an ellipse, or equivalently a positive definite symmetric matrix, to a polygon that is different from other better known ways. We want to know ...
22
votes
13answers
4k views

Generalizations of the Birkhoff-von Neumann Theorem

The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices. The question is to point out different ...
22
votes
5answers
789 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 ...
21
votes
3answers
2k views

How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set $\{1^{a_1} \cdot 2^{...
21
votes
4answers
763 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 ...
20
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 ...
19
votes
1answer
472 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 ...
18
votes
5answers
909 views

Is there a midsphere theorem for 4-polytopes?

The (remarkable) midsphere theorem says that each combinatorial type of convex polyhedron may be realized by one all of whose edges are tangent to a sphere (and the realization is unique if the center ...
17
votes
4answers
612 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 ...
17
votes
4answers
792 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 ...
17
votes
3answers
1k views

Cutting convex sets

Any bounded convex set of the Euclidean plane can be cut into two convex pieces of equal area and circumference. Can one cut every bounded convex set of the Euclidean plane into an arbitrary number $...
17
votes
2answers
638 views

“Derived” polyhedra and polytopes

The notion of derived polygon is natural and leads to remarkable convergence. Start with a polygon, and replace it by locating a point on every edge a fraction $\alpha$ between the two endpoints. For ...
17
votes
1answer
496 views

Egalitarian measures

A question I got asked I while ago: If $T$ is a triangle in $\mathbb R^2$, is there a function $f:T\to\mathbb R$ such that the integral of $f$ over each straight segment connecting two points in the ...
17
votes
5answers
451 views

How many unit simplices are needed to cover a unit $n$-cube?

The volume of an $n$-dimensional simplex of unit edge length is $$V(n) = \frac{\sqrt{n+1}}{n! 2^{n/2}} \;,$$ so at least $\lceil 1/V(n) \rceil$ such simplices are needed to cover the unit $n$-cube. ...
17
votes
2answers
802 views

About a Delzant polytope. (In particular dodecahedron)

Hi. I have a question. Definition. Delzant polytope $P$ is a rational convex simple polytope with the smooth condition. Here, "smooth" means that for each vertex $v$, the $n$ edges containing $v$ ...
17
votes
0answers
318 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 ...
16
votes
1answer
331 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., $\mathbb{...
16
votes
2answers
422 views

What is $A+A^T$ when $A$ is row-stochastic ?

This is motivated by this MO question. If $A\in{\bf M}_n({\mathbb R})$ is row-stochastic (entrywise non-negative, and $\sum_j a_{ij}=1$ for all $i$), then $M:=A+A^T$ is symmetric, entrywise non-...
15
votes
1answer
377 views

Does every convex polyhedron have a combinatorially isomorphic counterpart whose all faces have rational areas?

Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas? Does every convex polyhedron have a combinatorially isomorphic counterpart whose edges ...
15
votes
0answers
166 views

realization spaces of 3-dimensional polytopes

It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible. A proof of this theorem can be found for instance in ...
14
votes
4answers
1k views

Can you determine whether a graph is the 1-skeleton of a polytope?

How do I test whether a given undirected graph is the 1-skeleton of a polytope? How can I tell the dimension of a given 1-skeleton?
14
votes
2answers
896 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) ...
14
votes
1answer
616 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, etc.,...
14
votes
1answer
494 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 ...
14
votes
1answer
312 views

Smallest regular simplex containing the unit cube in $R^n$

What is the length $e_n$ of the edge of the smallest $n$-dimensional regular simplex $S_n$ containing the $n$-dimensional unit cube $Q_n$? In particular, is there $n$ such that $e_n<\sqrt{2}(n+...
13
votes
2answers
288 views

Can any simplex shadow-project to a regular simplex?

Every triangle $A$ can be oriented in $\mathbb{R}^3$ so that its orthogonal projection (shadow) onto the $xy$-plane is an equilateral triangle $Q$:               &...
13
votes
3answers
673 views

Triangulations of polyhedra

A topologist came to me with this question, but everything I think should work doesn't. How many triangulations are there of a polyhedron with n vertices? By a "triangulation" of a polyhedron P we ...
13
votes
2answers
2k 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? ...
13
votes
1answer
434 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 ...
13
votes
2answers
3k 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$. ...
13
votes
2answers
1k views

Are the Platonic solids shadows of 4-polytopes?

Say that a 3D shadow of a 4-polytope is a parallel projection to 3-space, not necessarily orthogonal to that 3-space (that would make it an orthogonal projection). I am wondering if each of the five ...
13
votes
0answers
352 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?
13
votes
0answers
220 views

Does there always exist a self dual polytope that contains a given polytope contained in its dual?

Suppose a polytope $P$ is contained in its dual polytope $\tilde{P}$. Does there always exist a polytope $Q$ that contains $P$ and is self dual $Q=\tilde{Q}$? Is there any bound on the minimal number ...
12
votes
6answers
2k views

On the number of Archimedean solids

Does anyone know of any good resources for the proof of the number of Archimedean solids (also known as semiregular polyhedra)? I have seen a couple of algebraic discussions but no true proof. Also, ...