Questions tagged [polytopes]
In elementary geometry, a polytope is a geometric object with flat sides, which may exist in any general number of dimensions $n$ as an $n$-dimensional polytope or $n$-polytope.
759
questions
3
votes
2
answers
99
views
Can a point be closer to all the vertices of a convex polytope than another point inside that polytope?
Consider a set $X = \{x_i \in \mathbb{R}^n\}$ and denote its convex hull
$$
C \equiv \bigg\{ \sum_i \lambda_i x_i : \lambda_i \geq 0 \text{ for all } i \text{ and } \sum_i \lambda_i = 1 \bigg\}.
$$
I ...
- 33
0
votes
0
answers
29
views
Automorphism group of a Polytope
I have been given the following task: Let $P \subseteq \mathbb{R}^d$, a polytope, such that $P = \text{conv}(K)$ for $K \subseteq S^{d-1}$ finite, where $S^{d-1}$ denotes the Euclidean unit sphere in $...
- 23
0
votes
0
answers
30
views
Why is the hypercube also called the "measure polytope"?
The title expresses my question.
Wikipedia says the term was originated by Elte in 1912, and Coxeter later
adopted the term
in his book Regular Polytopes, using the symbol $\gamma_n$ for the $n$-cube [...
- 30.2k
-1
votes
1
answer
47
views
Conditions for equidistant points in space
Given a set of n distinct points in space, where n is a natural number greater than 1, what is the geometric structure that results from connecting each point to every other point with straight lines ...
2
votes
2
answers
57
views
Dimension of a polytope cut with a hyperplane
Let $P \subseteq \mathbb{R}^d$ be a convex polytope and let $H \subseteq \mathbb{R}^d$ be a hyperplane with two sides $H^+$ and $H^-$. Let $V$ be the vertex set of $P$. Suppose $V = A \cup B$ where $A$...
1
vote
0
answers
29
views
Slicing edges out of a high dimensional polytope.
Let us start in 3D. Say I give you a polytope cone and you slice one of its edges out, like in this picture:
(i.e. you grab a plane that passes through it's apex and cut off a single edge)
Let's make ...
- 3,088
0
votes
0
answers
21
views
Can a polytope cone always be embedded in 2D?
Assume you have $k$ half spaces which all intersect at the same vertex forming a cone.
In 2D this forms just a point as no other point exist inside the cone.
In 3D this forms a pyramid with a ...
- 3,088
0
votes
0
answers
21
views
How to find which sets of hyperplanes intersect on valid lines?
Let us say that you have a large (large compared to the dimension) number of hyperplanes which all intersect at a point.
These planes produce a hyper-cone in whatever dimension we are working with. ...
- 3,088
1
vote
0
answers
23
views
Enumerating all edges from a vertex in an H-representation of a polytope?
Description
Let's say I give you a convex polytope in $h-$representation, i.e. $Ax \leq b$, with $A \in \mathbb{R}^{m \times d}$. For now let's assume $d=3$.
A vertex $v$ is non-degenerate if there ...
- 3,088
0
votes
0
answers
24
views
Getting a V-Representation from an H-representation of a polytope?
I am trying to find an easy to follow resource on implementing any (reasonable) algorithm to find a V-represnetation of a polytope from its h-representation. I only need this to work for $\mathbb{R}^...
- 3,088
3
votes
0
answers
62
views
What is special about the 11-cell and 57-cell?
Reading about the 11-cell and 57-cell I find two facts implied often:
They are particularly notable among the abstract regular 4-polytopes.
They are related to each other.
I'll establish why I think ...
- 2,188
0
votes
0
answers
30
views
Is there such a thing as a convex polytope defined over a mixed-variable space: $\mathbb{Z}^m \times \mathbb{R}^n$
I am currently learning about polytopes and I have reached the stage of convex polytopes. Wiki says that a
convex polytope is a special case of a polytope, having the additional property that it is ...
- 712
0
votes
0
answers
24
views
Counting lattice points in cross-sections of a polytope
Let $P$ be polytope in $\mathbb{R}^d$ with vertices in $\mathbb{Z}^d$ and let $h(z_1,\ldots,z_d)\in\mathbb{Z}[z_1,\ldots,z_d]$ be a degree one polynomial with integer coefficients, thought of as a &...
- 944
4
votes
0
answers
57
views
Ant walking on a cube riddle generalization to higher dimensions
There's a pretty common riddle floating around which goes something like this:
An ant starts at one corner of a unit cube. They wish to reach the opposite corner. If they can traverse along any face, ...
- 41
1
vote
1
answer
102
views
Knowing if the finite intersection of half spaces forms a closed polytope?
Say you have $N$ half-spaces $P$ in some dimension. We want to know if the intersection of all such half spaces results in a closed or open polytope, and if open, we want to introduce the minimum ...
- 3,088
5
votes
0
answers
69
views
Which manifolds admit symmetric tilings?
Let $M$ be a connected, boundaryless manifold. A tiling of $M$ is a regular cellulation of $M$, and a tiling is regular (i.e. symmetric) if the group of self-homeomorphisms of $M$ that map cells to ...
- 10.2k
2
votes
1
answer
56
views
To cut a square pyramid in half by a plane parallel to one of its lateral faces
The image below depicts a pyramid $ABCDE$ with a square base. It is to be cut by the plane $FGHI$ which is parallel to the face $ADE$, such that this plane cuts the pyramid in two halves. Find the ...
- 17.3k
0
votes
0
answers
16
views
Simplicial polyhedral fans and shellability
A simplicial polyhedral fan $\Sigma \subseteq \mathbb{R}^n$ is a collection of simplicial polyhedral cones $\{\alpha_1 v_1 + \dots + \alpha_r v_r : \alpha_r \geq 0\} \subseteq \mathbb{R}^n$, where the ...
0
votes
1
answer
28
views
When does a smooth projective toric variety admit a symplectic structure?
I'm trying to understand the relationship between toric varieties and their associated polytopes. There is a very crisp result in the case of symplectic toric varieties, namely that there is a 1:1 ...
- 183
0
votes
0
answers
20
views
Properties of the Transportation Problem Polytope
In the transportation problem, we have a set of $ k $ warehouses with a supply of $ a_{i} > 0 $ for $ i \in\{1, \ldots, k\} $, and $ \ell $ customers with a demand of $ b_{j} > 0 $ for $ j \in\{...
- 560
0
votes
0
answers
28
views
Which simplicial complexes are completely determined by the 1-skeleton of their dual cell complexes?
Consider the following line of reasoning that shows certain simplicial complexes (of arbitrary dimension) are completely determined by corresponding graphs:
The facet complex of any simplicial ...
- 1,280
1
vote
1
answer
86
views
Is the tetrahedron is the unique polytope having the property that all its vertices are adjacent?
$\textbf{Definition 1:}$ A polytope $P \subseteq \mathbb{R^n}$ is the convex hull of a finite points $x_1,...,x_n \in \mathbb{R}^n$, i.e, $P=\text{conv}(\{x_1,...,x_k\})$. The dimension of P is the ...
0
votes
0
answers
24
views
Every regular apeirohedron is genus 0 or ∞
I'm looking for a proof of or counterexample to the following conjecture:
Every regular apeirohedron is genus 0 or ∞.
Here I mean an apeirohedron to mean a rank 3 abstract polytope with an infinite ...
- 2,188
0
votes
0
answers
14
views
How to know if a set of halfplanes in 3D form a closed polytope and close the polytope if they don't?
We will define a polytope $\Pi$ as the finite intersection of $n$ half spaces. That is, given $n$ half spaces defined by a position and a normal $P_i = (\vec p_i, \vec n_i)$, then
$$\Pi = \cap^n_{i=1}...
- 3,088
3
votes
0
answers
53
views
Relation between volume of a convex polytope and its width
Let $P=\{x\in \mathbb{R}^n\mid a_i^\top x\leq b_i,\, i=1,\ldots,m\}$ be a bounded convex polytope, $\|a_i\|_2=1,\, i=1,\ldots,m$. Let us define the width of $P$ in the direction $a_i$ as
$$
\...
- 95
0
votes
1
answer
53
views
How can I check is this set convex?
I have a set of linear combinations ;
$$L = \left\{ (x_1,x_2,x_3) \mid 2 x_1 + x_2 + 2 x_3 \geq 5, x_3 \geq x_1, x_1 \geq 0 \right\}$$
and wanted to show this set is convex or not. I followed this way;...
- 115
1
vote
1
answer
48
views
Almost regular complex polytopes
Within his 2nd edition of "Regular Complex Polytopes" Coxeter seems to have added a section about "Almost Regular Polytopes". I for one do not have access to that book, all I can ...
- 4,021
2
votes
0
answers
57
views
Is there a convex polyhedron all of whose 2D polygonal cross sections are asymmetrical?
Define a nondegenerate convex n-polytope as the convex hull of a finite number of points in Euclidean n-space, such that its interior is nonempty.
It seems true that every nondegenerate convex ...
- 21
0
votes
0
answers
15
views
The connectivity of reflexive polytopes from just their vertices?
I'm working with the Kreuzer-Skarke database of 4-dimensional reflexive polyhedra. It lists almost half a billion polytopes, each represented by its vertex list and a few properties (Hodge numbers and ...
- 1
5
votes
1
answer
224
views
Is a piecewise linear function always a sum of concave and convex functions?
If I take a piecewise linear function (piecewise affine) is it true that I can always write it as a sum of concave and convex functions?
My understanding of this page
https://mjo.osborne.economics....
- 159
0
votes
0
answers
32
views
real space embedding of complex polytopes
Because of $\mathbb C^n = \mathbb R^{2n}$ complex polytopes ought be embeddable as substructures of real space polytopes (with doubled up dimensionality).
Look, complex edges do have $m\ge2$ vertices ...
- 4,021
2
votes
0
answers
32
views
How to find a set of linear inequalities from the vertices of a $d$-dimensional convex polytope?
Let $S = \{x_0, \dots, x_n\} \subseteq (\mathbb{R}^+)^{d}$ be the set of vertices of a convex $d$-dimensional convex polytope ($d \geq 2$).
I am interested in finding a set of linear inequalities such ...
- 21
1
vote
4
answers
100
views
operants on complex polytopes
I would assume that complex polytopes (according to Shephard and Coxeter) too could be alternated (snubbed), rectified, truncated, etc. - possibly given some further restrictions.
However I have ...
- 4,021
2
votes
1
answer
44
views
Any face of a polytope is an intersection of the defining half-spaces
Let $P$ be a polytope in $\mathbb{R}^d$ given as the solution set to a system of linear inequalities $a_ix \le c_i$ for some row vectors $a_i$ and scalars $c_i$, $i = 1,\dots,n$. For each $i$ define $...
0
votes
0
answers
39
views
Birkhoff polytope vs permutation polyhedron
I cannot understand a few things about the Birkhoff polytope.
The Birkhoff polytope is defined as a polyhedron of all $n \times n$ doubly stochastic matrices. How is is it polytope then? To transform ...
- 1
1
vote
0
answers
36
views
Simplification and "average" of polytopes
I have multiple (convex and bounded) polytopes, all of them describing the feasible area of a given LP (the rest of the LP is always the same), for a number of scenarios. Since those polytopes are too ...
- 21
1
vote
1
answer
75
views
Polytopes: affine isomorphism implies combinatorial isomorphism
Let $P \subseteq \mathbb{R}^d$ and $Q \subseteq \mathbb{R}^e$ be (convex) polytopes. Define them to be affinely isomorphic if there is an affine map $f \colon \mathbb{R}^d \to \mathbb{R}^e$ whose ...
0
votes
0
answers
38
views
Volume over affine transformations across dimensions.
My understanding is that, for an affine transformation with square matrix $T$, the volume of a set transformed through this affine transformation gets scaled by |det($T$)|. However, if $T$ is ...
1
vote
1
answer
49
views
Are there any names yet for this kind of polytope? [closed]
Are there any names yet for this kind of polytope (either the 3D or 4D instance): A half of the hypercube $[-1,1]^n$ cut by the hyperplane $\sum_{i=1}^n x_i = 0$?
The 3D instance is a polyhedron with $...
- 11
3
votes
1
answer
35
views
Intuition for Projective Transformations $\mathbb{R}^d\to\mathbb{R}^d$
I am reading through the first chapter of Grunbaum's book Convex Polytopes, in which he gives the following definition of projective transformations $\mathbb{R}^d\to\mathbb{R}^d$:
$$Tx = \frac{Ax + b}{...
- 43
0
votes
0
answers
58
views
Numerical check that a polytope is small
I have a polytope $S$ defined by linear equations.
Ideally, I would like to show that my polytope contains only 1 point.
To do that, I could maximize and minimize each of the $n$ variables.
However I ...
- 271
3
votes
0
answers
35
views
Upper bound to Smallest volume lattice polytope containing a hypersphere?
Let $S$ be a hypersphere of radius $r$ in $\mathbb{R}^n$ whose centre may or may not be a lattice point (i.e. a point in $\mathbb{Z}^n$). Can you give any upper bound to the volume of the smallest ...
- 2,410
3
votes
2
answers
52
views
Suppose $P_1$ and $P_2$ are two $n$-dimensional convex polytopes. Does $\partial P_1 \subseteq\partial P_2$ imply that $P_1 = P_2$?
Given two convex polytopes $P_1$ and $P_2$ with the same dimension, I want to know if the boundary of $P_1$ (denoted $\partial P_1$) being contained in the boundary of $P_2$ (denoted $\partial P_2$) ...
- 1,584
2
votes
1
answer
39
views
Iterating Lattice Points inside a Parallelepiped in $\mathbb{R}^n$
I have an invertible matrix $M\in\mathbb{R}^{n\times n}$ and I have a hypercuboid $I=I_1\times\ldots\times I_n$ which is a cartesian product of closed intervals, and I want to find all lattice points ...
- 6,325
0
votes
0
answers
27
views
About the number of faces of the conification of a polytope
Let $P\subset\mathbb{R}^n$ be a polytope of dimension $(n-1)$ such that the origin $\vec{0}\not\in\text{Aff}(P)$, where $\text{Aff}(P)$ denotes the affine hull of $P$ in $\mathbb{R}^n$. Now, we ...
- 363
1
vote
0
answers
34
views
Upperbounding the Hausdorff distance between two scaled polytopes
This post appears to answer my question. However, it seems that I misunderstand the answer and or problem it solves. (I try to keep the notation consistent w.r.t to post I am referring to)
Suppose I ...
- 71
2
votes
2
answers
66
views
Proof that the Szilassi polyhedron is not abstractly regular
The Szilassi polyhedron has seven hexagonal faces and 14 trihedral vertices. This is enough to make it a "regular toroid" in according to Szilassi.[1] However abstract polytopes are required ...
- 2,188
0
votes
0
answers
69
views
Finding adjacent vertices on a convex polytope, searching among basis exchanges?
My question is about how, in general, to go from one vertex of a convex polytope to an adjacent one. But also I have more conceptual questions about how the simplex method works.
Say I have a linear ...
0
votes
0
answers
13
views
If two combinatorial polytopes have a subset of their cocircuits in common, will they have a triangulation in common?
In "Triangulations" by Loera, Rambau, and Santos, there is a Corollary (4.1.44) that states that two combinatorially equivalent (having the same oriented matroid) point configurations have ...
- 1
1
vote
0
answers
26
views
Generalizing section-based operations on abstract polytopes
While writing some code to explore abstract polytopes, I've noticed that many intuitive polytope operations (like the Conway polyhedron operations) can be obtained by defining the output polytope $Q$ ...
- 10.2k