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
1
vote
0answers
21 views

Confining a polytope to one side of an affine hyperplane

Judging whether one convex polytope is inside of another when both are expressed as a system of linear inequalities seems to be a complex problem. This answer on math.stackexchange.com claims the ...
3
votes
1answer
149 views

Iterating projections to random halfspaces

Consider the following process: Start with a set $S = \mathbb R^n$. Repeat $L$ times: choose a random orthonormal basis $u_1, \ldots, u_n$, and consider the cone $C = \{ \sum \alpha_i u_i : \alpha_i \...
0
votes
0answers
54 views

Integer Fourier-Motzkin elimination of special polyhedron

I have a set of integral points in a convex region $$P_0=\{(x,y)\in\mathbb Z^{m'+n}:\mbox{ }A[x,y]'\leq b\}$$ where $P_0$ is identical to $P_1$ below $$P_1=\{x\in\mathbb Z^n:\exists\mbox{ exactly one }...
4
votes
0answers
83 views

“Baues poset” of shellings of simplicial polytope?

Let me start with some background I want to use as analogy. Consider a (convex) polytope $P$ and its set of triangulations. Among all the triangulations, a well behaved subset are the regular ones: ...
14
votes
1answer
474 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-...
0
votes
0answers
59 views

On number of facets in projected polytopes of certain sparseness

$\DeclareMathOperator\Set{Set}$ Let $Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$ where $A$ has $r=km$ rows and $k=O(1)$. I am trying to write $$ Set=\{x\in\...
7
votes
0answers
75 views

Can solutions to Thomson's problem have pentagons?

Thomson's problem asks for the minimum energy configuration for $N$ electrons on a sphere (refs: https://en.wikipedia.org/wiki/Thomson_problem, https://sites.google.com/site/adilmmughal/...
1
vote
0answers
41 views

Decomposition of Polyhedral - An example

There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system $$ \...
14
votes
1answer
523 views

Inequalities for marginals of distribution on hyperplane

Let $H = \{ (a,b,c) \in \mathbb{Z}_{\geq 0}^3 : a+b+c=n \}$. If we have a probability distribution on $H$, we can take its marginals onto the $a$, $b$ and $c$ variables and obtain three probability ...
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 ...
2
votes
1answer
104 views

Anchor sets for lattice polygons: Part I

Suppose $V=\{(x_1,y_1), (x_2,y_2),\dots,(x_v,y_v)\}$ is a vertex set of lattice points satisfying $$0=x_1<x_2<\dots<x_v \qquad \text{and} \qquad y_1>y_2>\cdots>y_{v-1}>y_v=0.$$ ...
5
votes
2answers
85 views

Partitions of convex planar regions into zonogons

A zonogon is a centrally symmetric convex polygon. Are there convex non-zonogons that can be partitioned into a finite number of (convex) zonogons? Same as 1 with the pieces allowed to be nonconvex ...
1
vote
1answer
74 views

Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]

Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
3
votes
0answers
63 views

Additional symmetries of the Traveling Salesman Polytope

Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
14
votes
2answers
298 views

Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?

For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices $$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\ \pi_{2,1} & \ddots & \...
2
votes
1answer
58 views

Are zonotopes determined by their edge-graph?

General polytopes are not determined by their edge-graph (up to combinatorial equivalence). But I came accross the statement that zonotopes are determined in this way. Question: Is this true? And ...
3
votes
1answer
153 views

Cohomology ring of a hypersurface in toric variety

Let $X^n$ be a smooth projective toric variety corresponding to a simple polytope $P$. It is well known that the cohomology ring $H^*(X)$ can be described in terms of combinatorics of faces of $P$. ...
8
votes
1answer
175 views

Are there centrally-symmetric self-dual polytopes in dimension $d> 4$?

A convex polytope $P\subset\Bbb R^d$ is centrally symmetric if $-P=P$. It is self-dual (or better, self-polar?) if its polar dual $P^\circ$ is congruent to $P$, that is, there is a map $X\in\mathrm O(\...
0
votes
1answer
64 views

If there are eigenvectors with largest components $i$ resp. $j$, then is there an eigenvector with two largest components $i$ and $j$?

Let $G=(V,E)$ be a connected (finite simple) graph with vertex set $V=\{1,...,n\}$ and let $\theta_2\in\Bbb R$ be the second-largest eigenvalue of its adjacency matrix. I wonder about the following ...
2
votes
1answer
92 views

Minimum Euclidean squared norm in the convex hull of points with rational coordinates

This is probably known, but I have not located a reference. Let $P$ be the convex hull of $k$ points in $\mathbb R^n$ with rational coordinates. Consider the Euclidean square norm function $F:P\to\...
7
votes
2answers
296 views

Can two non-equivalent polytopes of same dimension have the same graph?

By a polytope I mean the convex hull of finitely many points. The graph of a polytope is the graph isomorphic to its 1-skeleton. By equivalence of polytopes I mean combinatorial equivalence, i.e. ...
4
votes
2answers
110 views

Existence of a fundamental domain for the convex hull of group action on a rational polytope

Let $P \subset \mathbb R^n$ be a compact rational polytope (the affine space spanned by $P$ may not be $\mathbb R^n$). Let $G \subset {\bf GL}(n,\mathbb Z)$ be an arithmetic group. Let $$C = {\rm Conv}...
2
votes
1answer
73 views

State-of-the-art article on “uniform 5-polytopes?”

I would like to read article(s) that provide the “state of the art” on the following open problem: “Enumerate all convex uniform 5-polytopes.” This problem is posted on the “Open Problem Garden” (http:...
3
votes
1answer
166 views

What are midway sections of simplices?

This is a (slightly modified) crosspost. Subsequent edit - coordinates are changed to obtain simpler expressions; the existing answer is not affected. There is a family of convex polytopes: $P_n$ is $...
0
votes
0answers
34 views

Attached convex “hulls”

Let $\mathcal{P}$ a finite set of points of a Euclidean $\mathbb{E}^n$ and take the union $\mathrm{U}(\mathcal{P})$ of all closed half-spaces defined by $n$ elements of $\mathcal{P}$ that contain only ...
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 ...
7
votes
2answers
114 views

Constructing a $0/1$ polytope from an abstract simplicial complex

Let us fix $\Delta$ a finite simplicial complex, and label the vertices of $\Delta$ as $\{1,2,\ldots,n\}$. For each $F\in \Delta$ let us consider the point in $\mathbb{R}^n$ given by: $$e_F := \sum_{i\...
5
votes
1answer
139 views

Is there a polytope with an essentially unique shape?

More percisely: Question: Is there a (convex) polytope that has a unique realization up to, say, projective transformations? I suppose I have to assume that it has more than $d+2$ vertices/facets if ...
4
votes
2answers
167 views

Is there more than one pseudo-Catalan solid?

This question was asked on MSE a year ago. Motivation for this question can be found in other MSE questions here, here or here. Convex solids can have all sorts of symmetries: the platonic solids are ...
12
votes
1answer
682 views

Two questions on the permutohedron

The $n$-dimensional permutohedron $P_n$ is the polytope given by the convex hull of all the possible permutations of the vector $(1,2,\dots,n+1)\in\mathbb{R}^{n+1}$. So it has $(n+1)!$ vertexes. I ...
3
votes
2answers
505 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 ...
3
votes
2answers
128 views

If a polytope is centrally symmetric and combinatorially equivalent to a zonotope, is it a zonotope?

A zonotope is a polytope whose 2-faces are centrally symmetric. Question: If a polytope $P$ is centrally symmetric and combinatorially equivalent to a zonotope, is it itself a zonotope?
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 ...
3
votes
1answer
257 views

An example in symplectic geometry

$\DeclareMathOperator\SU{SU}$Let $M$ be a coadjoint orbit of dimension 6 of $\SU(3)$, and let $T$ be the maximal torus in $\SU(3)$. If we denote $\mu : M \longrightarrow \mathbb{R}^2$ the moment map ...
3
votes
1answer
92 views

Maximal number of visible vertices

Let $P$ be a three-dimensional convex polytope with $N$ faces; $O$ a point outside $P$. What is the maximal number $f(N)$ of vertices of $P$ which may be seen from $O$?
3
votes
0answers
102 views

Edges in the convex hull of the union of random polygons

Let $P$ and $Q$ be two convex polygons in $\mathbb{R}^2$. Given $a > 0$, denote by $aP$ its image under the dilation by $a$ centered around the origin (i.e. the polygon obtained by replacing each ...
4
votes
1answer
226 views

Polynomial size embeddings of toric varieties from polytopes?

Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan. $X_P$ is always projective, because the collection of characters corresponding to the points $\...
0
votes
0answers
32 views

Conditions on $a_i,b_i$ for $i =1,\ldots,n$, so that $\arg\max_{\|x\| \le 1}\min\{a_i^\top x + b_i\mid i = 1,\ldots,n\} \subseteq \{\|x\| < 1\}$

Let $A$ be an $n \times m$ matrix with rows $ a_1,\dots,a_n \in \mathbb R^m$ and let $b=(b_1,\dots,b_n)$ be a vector in $\mathbb R^n$. Let $\mathbb B_m$ be the centered closed unit-ball in $\mathbb R^...
4
votes
0answers
390 views

Convex polytopes as “products” of lower dimensional polytopes of the same family

This MO-Q details the sense in which an associahedron is a product of lower dimensional associahedra, and this MSE-Q indicates the same is true for permutohedra. Is there a reference which classifies ...
0
votes
1answer
93 views

If $C_1\subseteq C_2$ are two closed convex cones that are pointed with $\partial C_1\subseteq \partial C_2$ then is $C_1=C_2$?

Let $C_1$ and $C_2$ be two proper full dimensional closed convex cones in $\mathbb{R}^n$ that are pointed. Suppose that $C_1\subseteq C_2$ and that the boundary of $C_1$ is contained in the boundary ...
1
vote
1answer
91 views

Exact volume calculation of a polytope is NP hard under which restrictions?

Computing the exact volume of a polytope given in half space representation seems to be NP-hard. One paper I found proved it is hard for rational coefficients. (However, the paper itself was behind a ...
4
votes
1answer
61 views

Mass distributions for high dimensional simplex and cross polytope

In this question, it is shown that the radial mass distribution of an $n$-cube (i.e. the probability density for the distance from a point selected uniformly from within an $n$-cube to the cube's ...
6
votes
1answer
159 views

Edges of the contact polytope of the Leech lattice

Let $P\subset\Bbb R^{24}$ be the contact polytope of the Leech lattice, that is, $P$ is the convex hull of the 196,560 shortest vectors of $\Lambda_{24}$. Question: What are the edges of $P$? Let'...
3
votes
0answers
52 views

How to find the dimension of the polar cone of a convex cone generated by some given vectors

Suppose we have access to a generating set $\{v_1, ..., v_k\}\subseteq\mathbb{R}^n$ of the convex cone $C=cone(v_1, ..., v_k)$, where $cone(\cdot)$ is the conical hull (i.e. nonnegative span) of ...
2
votes
1answer
46 views

Is there a non-orthogonal linear deformation of a polytope that preserves edge-lengths and vertex-origin-distances?

Is there a polytope $P\subset\Bbb R^d$ (convex hull of finitely many points, not contained in a proper affine subspace), and a linear, but non-orthogonal transformation $T\in\mathrm{GL}(\Bbb R^d)\...
4
votes
3answers
247 views

Minimal data required to determine a convex polytope

Let $P\subset \Bbb R^d$ be a convex polytope. Suppose that I know its combinatorial type (aka. the face-lattice), the length $\ell_i$ of each edge, and the distance $r_i$ of each vertex from the ...
9
votes
0answers
145 views

How to correctly state Cauchy's rigidity theorem?

Cauchy's rigidity theorem is usually cites briefly as Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent. As a more formal generalization to general ...
4
votes
0answers
87 views

The area of cross-section of polyhedron or polytope

Consider a polyhedron or polytope $P$ in $\mathbb{R}^n$. Let $F$ be a bounded face of $P$. Now we shift and rotate this polyhedron such that $F$ lies on the hyperplane $\{t=0\}$, and $P\subseteq\...
5
votes
0answers
59 views

Which polytopes can be deformed while keeping their edge-lengths?

Let $P\subset\Bbb R^d$ be a convex polytope (a convex hull of finitely many points). Lets call it flexible, if it can be continuously deformed while keeping its combinatorial type, and keeping its ...
9
votes
2answers
188 views

Integer decomposition property with a partial order

Let $\mathcal{P}$ be a convex lattice polytope in $\mathbb{R}^n$. We say that $\mathcal{P}$ has the integer decomposition property (or "is IDP") if for all $k\in \mathbb{N}$ and $\alpha \in ...

1
2 3 4 5
16