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
916
questions
72
votes
2
answers
9k
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 ...
63
votes
8
answers
14k
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$...
57
votes
14
answers
18k
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 ...
55
votes
5
answers
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 ...
55
votes
1
answer
3k
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 $\...
54
votes
5
answers
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
3
answers
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 ...
48
votes
4
answers
3k
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 ...
45
votes
4
answers
5k
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 ...
45
votes
1
answer
3k
views
two tetrahedra in $\mathbb R^4$
It is relatively easy to show (see below) that if we have two equilateral triangles of side 1 in $\mathbb R^3$,
such that their union has diameter $1,$ then they must share a vertex.
I wonder whether ...
44
votes
11
answers
25k
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 ...
36
votes
2
answers
2k
views
Bodies of constant width?
In two-dimensional case one can generalize figures of constant width as figures which can rotate in a convex polygon.
Here is one example which can be used to drill triangular holes:
I would like to ...
34
votes
16
answers
7k
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 ...
33
votes
2
answers
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
0
answers
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
4
answers
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, ...
31
votes
2
answers
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 ...
29
votes
7
answers
3k
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 ...
29
votes
0
answers
3k
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 ...
28
votes
1
answer
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 ...
27
votes
3
answers
12k
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 ...
26
votes
2
answers
4k
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
...
25
votes
7
answers
9k
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}^...
25
votes
4
answers
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
3
answers
964
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 ...
25
votes
2
answers
680
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
2
answers
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
4
answers
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
1
answer
716
views
Given a group action on a simplex, can I always find a fundamental region that is a simplex?
Let $\Delta\subset\Bbb R^n$ be a simplex with $n+1$ vertices. Let $G\subset\mathrm{GL}(\Bbb R^n)$ be a finite group of linear symmetries of $\Delta$, i.e. linear transformations that fix the simplex ...
24
votes
1
answer
590
views
Polytope where each vertex belongs to all but two facets
Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a ...
24
votes
1
answer
1k
views
Which unfoldings of the $d$-dimensional hypercube tile $(d{-}1)$-space?
A six year old question,
Which unfoldings of the hypercube tile $3$-space?, has just been answered by
Moritz Firsching:
All $261$ unfoldings tile space!
So now we know:
For $d=2$, the unfolding of ...
23
votes
3
answers
3k
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^{...
23
votes
1
answer
642
views
Covering the unit sphere in $\mathbf{R}^n$ with $2n$ congruent disks
Let $v_i$ be $2n$ points in $\mathbf{R}^n$, with equal distance $|v_i|$ from the origin. Suppose that the convex hull of these points contains the unit ball. Is it known that $|v_i|\geq\sqrt{n}$? ...
22
votes
5
answers
1k
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 ...
22
votes
1
answer
671
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$ ...
21
votes
4
answers
3k
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?
21
votes
3
answers
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) ...
21
votes
5
answers
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 ...
20
votes
4
answers
906
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 ...
20
votes
1
answer
872
views
Tetrahedra passing through a hole
Assume a plane $P\subset\mathbb R^3$ has a hole $H$, and that the hole is topologically a compact disc. Being so, $P\setminus H$ does not separate the space. A regular tetrahedron $\sigma^3$ (of edge-...
20
votes
5
answers
1k
views
From convex polytopes to toric varieties: the constructions of Davis and Januszkiewicz
One of the most useful tools in the study of convex polytopes is to move from polytopes (through their fans) to toric varieties and see how properties of the associated toric variety reflects back on ...
20
votes
1
answer
575
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
2
answers
7k
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}, \...
19
votes
1
answer
867
views
Can every simple polytope be inscribed in a sphere?
It is known that not every convex polytope (even polyhedron, e.g. this one) can be made inscribed, that is, we cannot always move its vertices so that
all vertices end up on a common sphere, and
the ...
19
votes
3
answers
2k
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
2
answers
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
0
answers
551
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
1
answer
616
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
2
answers
953
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
1
answer
637
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 ...