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.
804
questions
0
votes
0
answers
23
views
Is there a concise method for shifting the integration bounds of polytopes in multidimensional integrals?
I'm looking to better understand a change of variables/u-substitution for multidimensional integrals over regions determined by polytopes. For example, I know that
$$ \int^{1}_{0} dz \int^{1-z}_{0} ...
- 31
2
votes
0
answers
69
views
What is the smallest area of a central section of the unit hypercube?
Let $\mathcal{U} \subseteq \mathbb{R}^n$ denote the unit hypercube i.e. $\mathcal{U} = [0,1]^n$, and assume that for some $d \in \mathbb{R}^n$ one denotes by
$$
\mathcal{H} = \left\{x \in \mathbb{R}^n ...
- 1,311
1
vote
1
answer
39
views
Deriving an $f(k,n)$ giving the fraction of the hypervolume enclosed by the convex regular $n$-polytope with $k$ facets enclosed only by its insphere
Let $P$ be a convex regular polytope, whose insphere is an $n$-sphere with radius $R$
Define:
$\operatorname{Vol}(B^{n+1};R)$ denotes the hypervolume enclosed by the $n$-sphere of radius $R$
$\...
- 977
1
vote
0
answers
47
views
Where can I find the classification/name for this abstract polyhedra?
Edit: It seems this shape is a "stacked abstract non-convex polytope." This should have a name or Schafli symbol given that it's basically $4$, $\lbrace2,\infty \rbrace$-gons that mutually ...
- 104
1
vote
1
answer
66
views
Maximum number of vertices when dividing the $d$-dimensional simplex into $n$ convex polytopes.
The question is essentially in the title, but to be more precise: I would like to find the maximum number of vertices (i.e. distinct points of intersection) produced when splitting up the $d$-...
0
votes
1
answer
32
views
Polytopes with identical facets
Hypercubes have hypercube facets. Higher dimensional permutohedra have facets with identical facets related to hexagonal prisms (Permutohedron Facets).
Is it possible to characterize the polytopes ...
- 201
3
votes
2
answers
91
views
Not understanding or visualizing 4d polytopes at all
In my Euclidean geometry class, one of our final topics was the idea of polytopes, in particular 4D figures. We were told to visualize the hypercube as glued slices of squares, whereas the hypercube ...
- 639
6
votes
1
answer
334
views
What is the Number of Facets of a $d$-Dimensional Cyclic Polytope?
A face of a convex polytope $P$ is defined as:
$P$ itself, or
a subset of $P$ of the form $P\cap h$, where $h$ is a hyperplane such that $P$ is fully contained in one of the closed half-spaces ...
user1327750
1
vote
0
answers
70
views
Set dual with half-spaces [closed]
Let $X\subseteq \mathbb{R}^d,$ we define the set dual to
$X$, denoted by $X^*$, as follows:
$$X^*=\{y\in \mathbb{R}^d \mid \langle y,x\rangle\leq 1, \forall x\in X\}.$$
Geometrically, $X^*$ is the ...
- 414
4
votes
1
answer
146
views
Simplicial Generalization of Pythagoras
I recently heard about a claim that
For a triangle in 3-space, its area squared equals the sum of squares of areas of its projections onto three pairwise orthogonal planes.
I currently don't have ...
- 4,618
0
votes
0
answers
20
views
Intersection of interiors of sets in a partition of $\mathbb{R}^d$
Let $\mathcal{Q}=\{Q_1,...,Q_n\}$ and $\mathcal{P}=\{P_1,...,P_m\}$ be partitions of $\mathbb{R}^d$ with $n<m$. Assume all $Q_k\in\mathcal{Q}$ and $P_i\in\mathcal{P}$ are close and convex sets. ...
- 377
0
votes
1
answer
29
views
Transformation of contraints given non-invertible transformation of variables
Given the transformation $Ax = y$ and constraints $Cx \le d$, how to obtain the resulting constraints on $y$ when $A$ is rectangular with unknown rank? I'm thinking along the lines of using the pseudo-...
2
votes
0
answers
37
views
For each vertex $v$ of a polytope $P$, is vertex $v$ the unique optimal solution to some linear program over $P$?
Is it true that for every vertex $v$ of a polytope $P$, three exists some linear programming specification with $P$ as the feasible region for which vertex $v$ is the unique optimal solution?
If this ...
- 21
1
vote
0
answers
54
views
Generalization of Foci of an Ellipse
The two foci of an ellipse $p, q$ are defined so that $d(x, p) + d(x, q) = c$ for some constant $c$ and all $x$ lying on the boundary of an ellipse.
In general, people have studied n-ellipses, where ...
- 61
0
votes
0
answers
19
views
Extension complexity - Equivalent definitions
I'm confused by two, apparently equivalent, definitions of extension complexity.
See the attached screenshot:
From: Sparse sums of squares on finite abelian groups
and improved semidefinite lifts
...
- 788
1
vote
0
answers
67
views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 11
1
vote
1
answer
66
views
Algorithms to Find Convex Combination Coefficients for a Point within a Convex Polytope Without Explicit Representation
Set Up: Let $P$ be a finite convex polytope. Assume that we do not have a representation for $P$ (like a V-, H- or Z-representation of $P$), all we have is an algorithm which can find a point of $P$ ...
- 23
1
vote
0
answers
51
views
Euler's formula for polyhedron [closed]
I'm curious about Euler's formula and how it applies to polyhedra. Specifically, I'm wondering if there are simple formulas or methods to figure out the number of vertices, faces, and edges for ...
0
votes
1
answer
25
views
Name of $d$-simplex with "orthogonal" complementary subsimplices
Three-dimensional space allows for the following sequence of tetrahedra:
The regular tetrahedron with $d+1$ vertices
The pyramid whose base is a triangle with $d$ vertices centered at $0$ in $\{x_3=0\...
- 181
0
votes
0
answers
25
views
Polar Set of a Polyhedra is a Polytope
I am having trouble to verify Proposition 2 from the following MIT OCW document:
Is there a way for us to see the equivalence of $C_1$ and $C_2$ simply through the definition? I do notice there was a ...
- 593
2
votes
1
answer
29
views
Number of vertices of product of polytopes
If one takes the product of a polytope $P_1$ with another polytope $P_2$, where $P_1$ has $n$ vertices and $P_2$ has $m$ vertices, will the product of the two polytopes have $mn$ vertices?
It is not ...
- 3,015
0
votes
1
answer
51
views
A question about compactness and polytopes
I saw a statement as follow:
Let $A$ be a compact set in $\mathbb{R}^n$, and $P\subset A$ a closed
subset of $A$. By compactness, to prove that $P$ is a polytope, it
sufffices to work locally about a ...
- 347
0
votes
0
answers
18
views
3-dimensional convex polytope with adjacent vertices is a 3-simlpex
Let $P=\rm{conv} ( \textit{V} )$ be an convex $3$-dimensional polytope with vertices $V$ in which every two vertices $x,y \in V$ are adjacent. Show that $P$ is a $3$-Simplex.
I think we can use radon'...
- 141
1
vote
1
answer
40
views
Circumradius of the intersection of two regular simplexes
For $n \geq 2$, let $\Delta^n$ be a regular $n$-dimensional simplex in $\mathbb{R}^n$ centered at the origin $0$ and inscribed in the unit sphere $\mathbb{S}^{n-1}$. Let $v_0,\dots,v_n \in \mathbb{S}^{...
- 147
2
votes
2
answers
89
views
Verify the formula for the the 3-simplex
One book I'm reading defines the regular 3-dimensional simplex as a subset of $\mathbb{R}^4$ as follows:
$$
\{\mathbf{x}=(x_1, x_2, x_3, x_4)\in\mathbb{R}^4: x_1+x_2+x_3+x_4=1, x_i\ge 0, i=\{ 1, 2, 3 ,...
- 617
5
votes
2
answers
466
views
What's the difference between zig-zags and helixes?
I've been reading through the Polytope-Wiki entry on helices. To my understanding, an $n$-gonal helix is a blend of a planar $n$-gon $\{n\}$ with the regular linear apeirogon $\{\infty\}$. The blend ...
- 1,928
2
votes
0
answers
49
views
Is there an algorithm for finding a geometric realization of a finite abstract simplicial complex [closed]
I have a $d$-dimensional finite abstract simplicial complex (ASC); that is I have a sequence of incidence matrices that define the complex. I know that any such ASC can be embedded in ${\mathbb R}^N$ ...
- 1,020
0
votes
0
answers
34
views
Why Are There Finitely Many Regular Polytope Compounds?
I'm interested in a proof of the finitude of regular compound polytopes (vertex, edge and face-transitive unions of regular polytopes) in dimensions greater than $2$. To be clear, I don't need an ...
- 2,346
2
votes
2
answers
109
views
Permutohedron Facets
The permutohedron P4 is the 3d truncated octahedron. Its facets consist of 6 hexagons and 8 squares.
The permutohedron P5 is a 4d polytope with 30 3d facets: there are 10 truncated octahedra, and 20 ...
- 201
2
votes
1
answer
56
views
Can a oblique antiprism be constructed?
Can a oblique antiprism be constructed?
Intuitively, it would seem oblique antiprism exist: Take any right antiprism and translate one of the parallel faces within it's plane.
I'm baffled, though, ...
- 4,470
0
votes
1
answer
72
views
Finding the extreme points of a polyhedron
Let $$X = \{ x \in \mathbb R^n: 1/2 \leq x_1 \leq 1 \text{ and } x_{i-1} \leq x_i \leq 2x_{i-1}\forall i=2,\ldots,n \}.$$ Prove that $X$ is a polyhedron and determine all of its extreme points.
My ...
- 679
0
votes
0
answers
28
views
Simplifying the set of constraints of an optimization problem
I’m currently working on a constrained optimization problem (the problem comes from the European Power Market) where the constraints define a solutions space which forms a complex polytope with many ...
- 1
0
votes
0
answers
41
views
Algorithm to recognize spherical abstract polytopes
A finite abstract polytope of rank 3 (an abstract polyhedron) consists of adjacency data for a collection of polygonal faces and their shared edges and vertices. This data is sufficient to uniquely ...
- 12k
2
votes
0
answers
52
views
Prove that $P_{\text {match }}(G) \cap\left\{x: 1^T x=k\right\}$ is the convex hull of all matchings in $G$ of size exactly $k$.
Problem: Prove that $P_{\text{match}}(G) \cap\left\{x: 1^T x=k\right\}$ is the convex hull of all matchings in $G$ of size exactly $k$.
My attempt:
Firstly, we prove that
$$\text{conv}\left\{\chi_M: M ...
- 1,248
2
votes
0
answers
20
views
One-to-one Correspondence of Facets of a Polytope [closed]
If the facets of a polytope $A$ are in one-to-one correspondence with the members of a finite set $X$ and the facets of a polytope $B$ are also in one-to-one correspondence with the members of $X$ (ie....
- 3,015
2
votes
0
answers
50
views
Techniques for convex optimization over a vertex-representation of a polytope?
I have a convex optimization problem where the feasible region is defined as the convex hull of a set of vertices. Even though the vertex set is in the low dozens of points, finding the half-space (H-...
- 121
2
votes
1
answer
110
views
Equivalence of Two Polytopes
I am trying to understand more about combinatorics and geometry of polytopes. If we create a pair of polytopes as below, they have the same number of facets (seven each) and they are combinatorially ...
- 3,015
0
votes
0
answers
31
views
Union of convex polytopes with non-linear upper bounds is till a convex polytope?
This is a follow-up of this.
Suppose I have a union set, $\bigcup\limits_{\{\mathbf{q}_k\}_{k=1}^n:\mathbf{q}_k \in\mathbf{P},\forall k\in\{1,2,...,n\}}A(\{\mathbf{q}_k\}_{k=1}^{n})$, where $A(\{\...
- 135
0
votes
0
answers
31
views
Is there a standard construction for Geodesic Polytopes in high dimensions?
Geodesic polytopes in $\mathbb R^3$ can be used to construct "simple" triangulations of $\mathbb S^{2}$, the 2-sphere. They can be constructed, for example, by taking a regular octahedron ...
- 164
1
vote
0
answers
48
views
Number of edges of polytope: what can be said?
Background: I am reading a paper (link) that concerns linear programs (with unknown constraints).
If a linear program has constraints $\mathbf A \mathbf x \leq \mathbf b$, where $\mathbf A \in \mathbb ...
- 125
3
votes
0
answers
111
views
Combinatorial equivalence of Minkowski Sum of two Polytope
On Page 8 (or Page 250 as mentioned in the article) of BASIC PROPERTIES OF CONVEX POLYTOPES, under the definition of Minkowski sum it is given that $P+\lambda P'$ is combinatorially equivalent for all ...
- 31
3
votes
2
answers
211
views
Infinite union of convex polytopes is till a polytope? (Union among probability simplex)
Suppose I have a union set, $\bigcup\limits_{\mathbf{q} \in\mathbf{P}}A(\mathbf{q})$, where $A(\mathbf{q})$ is a $n$-dimensional hypercube defined by
$$A(\mathbf{q}) = \left\{ \mathbf{x}\in\mathbb{R}^...
- 135
0
votes
0
answers
20
views
Representation of polytopes as intersection of halfspaces
Let $A \in \mathbb R^{m \times n}$ have rank $m < n$
On the way to showing that the condition (for $x \in \mathbb R^n$)
$A x = b$
$x \geq 0$
is equivalent to (intersection of halfspaces)
$\...
- 399
0
votes
0
answers
31
views
Volume of product of two Polyhedron P and Q
I have given two Polyhedrons $P$ and $Q$. What is the volume of their product $P \times Q = \{(p,q) \; | \; p \in P, q \in Q \}$.
If $P$ and $Q$ are cubes, then it would be $vol(P \times Q) = vol(P) \...
- 1
0
votes
0
answers
21
views
Bijection between basis of a constraint matrix and vertices of the feasible polytope
The Wikipedia article for the revised simplex method states
A vertex of the feasible polytope can be identified as a basis for $B$ for the
matrix $A$, chosen from the columns of $A$
Here, the ...
- 399
1
vote
0
answers
37
views
Clipping an n-dimensional polygon with a halfspace
Assume that I have a convex polygon in $n > 3$ dimensions, defined by a set of $m$ vertices $\{p_1,\dots,p_m\} \in \mathbb{R}^{n}$. Currently, I have defined my polygon as a set of edges between ...
- 961
2
votes
1
answer
51
views
Finding a bounding box for convex polytope, specified by linear inequalities
given a set of linear inequalities (and equalities) I want to find a bounding fox for it. There is an obvious straightforward solution, but I hope it is possible to convert the whole problem to one ...
- 147
0
votes
1
answer
39
views
Is an open set containing extreme points 0-dimensional?
I am currently reading through Lectures on convex geometry and have come across an argument that I cannot quite wrap my head around.
In the Proof of Theorem 1.22, the following construction is used:
...
- 165
1
vote
0
answers
43
views
Why this $2$-dimensional polytope has two different half-space representations? What is the geometrical intuition behind this?
Let a $2$-dimensional polytope given by the vertices $P_1=(0, -1)$, $P_2=(-1, 0)$, $P_3=(-1, 2)$, $P_4=(1, 0)$, $P_5=(1, -1)$:
When I use different libraries to obtain the half-space representation, ...
- 1,604
0
votes
1
answer
38
views
$n$-dimensional polytopes with $(2n)$-vertices that are not really prisms
Is there an $n\geqslant 3$ and a symmetric, convex polytope $V$ in $\mathbb R^n$ (symmetric means that if $x\in V$ then $-x\in V$ too) such that
$V$ has $2n$-vertices and
$V$ is not image of the ...
- 16.6k