Questions tagged [convex-polytopes]

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

Filter by
Sorted by
Tagged with
70
votes
2answers
8k 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 ...
57
votes
8answers
11k 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$...
54
votes
5answers
2k views

Unusual symmetries of the Cayley-Menger determinant for the volume of tetrahedra

Suppose you have a tetrahedron $T$ in Euclidean space with edge lengths $\ell_{01}$, $\ell_{02}$, $\ell_{03}$, $\ell_{12}$, $\ell_{13}$, and $\ell_{23}$. Now consider the tetrahedron $T'$ with edge ...
54
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 ...
54
votes
1answer
2k 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 $\...
52
votes
14answers
15k views

Open problems in Euclidean geometry?

What 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 ...
50
votes
3answers
3k 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 ...
47
votes
4answers
2k views

How many ways can you inscribe five 24-cells in a 600-cell, hitting all its vertices?

You can inscribe five tetrahedra in a dodecahedron so that each vertex of the dodecahedron is the vertex of just one tetrahedron, as drawn here by Greg Egan: Warmup question: How many ways can you do ...
43
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 ...
41
votes
4answers
4k 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 no one had ever ...
36
votes
10answers
19k 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 ...
35
votes
2answers
1k 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 ...
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 ...
32
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$, ...
31
votes
4answers
2k 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
2k 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 ...
27
votes
14answers
6k 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 ...
27
votes
1answer
1k views

Are Minkowski sums of upward closed “convex” sets in $\mathbb{N}^k$ still “convex”? (WAS: Comparing mana costs in Magic: The Gathering)

This was originally a question about comparing mana costs in Magic: The Gathering, but it's turned into a question about Minkowski sums of upward-closed convex sets in $\mathbb{N}^k$. The original ...
26
votes
7answers
2k views

Why are we interested in permutahedra, associahedra, cyclohedra, …?

The following families of polytopes have received a lot of attention: permutahedra, associahedra, cyclohedra, ... My question is simple: Why? As I understand, at least the latter two were ...
25
votes
4answers
1k 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 ...
25
votes
2answers
630 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 ...
25
votes
2answers
1k 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$ ...
25
votes
4answers
3k 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 ...
24
votes
3answers
825 views

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 faces all have rational areas? Does every convex polyhedron have a combinatorially isomorphic counterpart whose edges ...
24
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 ...
23
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^{...
22
votes
5answers
970 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 ...
20
votes
2answers
2k 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 ...
20
votes
1answer
414 views

Rational inscribed realization of the regular dodecahedron

While it is clear that the regular dodecahedron $D$ cannot be realized with all integer coordinates, it is easy to find a polytope, which is combinatorially equivalent (face lattice isomorphic) to $D$ ...
20
votes
1answer
535 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 ...
19
votes
3answers
2k 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) ...
19
votes
5answers
1k 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 ...
19
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 $...
19
votes
2answers
1k 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$ ...
19
votes
0answers
486 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 ...
18
votes
4answers
2k 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?
18
votes
4answers
771 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 ...
18
votes
1answer
556 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 ...
18
votes
4answers
916 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 ...
18
votes
2answers
791 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 ...
18
votes
1answer
602 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 ...
18
votes
5answers
567 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
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, ...
17
votes
7answers
6k views

Uniformly Sampling from Convex Polytopes

How to choose a point uniformly from a convex polytope $P \subset [0,1]^n$ defined by some inequalities, $Ax < b$? (Here $A$ is an $m \times n$ matrix, $x \in \mathbb{R}^n$, and $b \in \mathbb{R}^...
17
votes
4answers
446 views

Volume of convex lattice polytopes with one interior lattice point

Let $P$ be a convex polytope in $\mathbb{R}^3$ whose every vertex lies in the $\mathbb{Z}^3$ lattice. Question: If $P$ contains exactly one lattice point in its interior, what is the maximum possible ...
17
votes
1answer
514 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{R}^d$ ...
16
votes
5answers
1k views

Name of a polytope

What is the name of the polytope $\Sigma\cap (-\Sigma)$ for $\Sigma$ a $d-$simplex with barycenter at the origin? In dimension $2$, one gets a hexagon, in dimension $3$ an octahedron (given by the $6$...
16
votes
2answers
5k views

How many vertices can a convex polytope have?

One has an $n$-dimensional convex polytope $P$ represented by an intersection of half-spaces: \begin{equation}H_i = \{ (x_1,x_2, \ldots,x_n) \in \mathbb{R}^n \mid \sum_{j=1}^n a_{ij} x_j \ge a_{i0}, \...
16
votes
4answers
1k views

Can I build infinitely many polytopes from only finitely many prescribed facets?

Given a finite set of convex $d$-dimensional polytopes $\mathcal P$, for some $d\ge 2$. Question: Is it true that there are only finitely many different convex $(d+1)$-dimensional polytopes whose ...
16
votes
5answers
727 views

Rigidity of convex polyhedrons in $\mathbb R^3$ with faces removed

Take a convex polyhedron $P$ in $\mathbb R^3$ and remove all the faces, i.e. leave only the edges. Call this graph $E$. Let us now try to continuously deform $E$ in $\mathbb R^3$ so that all the edges ...

1
2 3 4 5
16