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.

Filter by
Sorted by
Tagged with
0
votes
0answers
16 views

Find the vertices of a convex polytope described by a system of linear inequalities

Given a $m\times n$ real number matrix $A$ and a $m\times 1$ real number matrix $a$. $Ax\le a$ describes a polytope. Is there a simple way to express the vertices or extremal points of this polytope?
3
votes
0answers
34 views
+50

Verifying algebraic construction of regular 4-polytopes

One nice way to construct the 24-cell and 120-cell is to take a tetrahedron or icosahedron, look its rotational symmetries (of order 12 or 60, respectively) in $\textrm{SO}(3)$, and pull them back ...
3
votes
1answer
22 views

Generalizing the apothem characterization of area for regular polygons, to convex regular polyhedra (and more?).

Recall: Given a convex, regular $n$-gon, of side length $s$, and apothem $a$, we may calculate its area $A$ as $$A = \frac 1 2a n s$$ or, if we let $P$ be the perimeter (i.e. $P=ns$), then we have the ...
10
votes
1answer
132 views

Do there exist uniform triangular prisms with all vertices in $\mathbb Z^3$?

It's quite easy to find a regular square prism (cube) or a regular triangular antiprism (octahedron) with vertices in $\mathbb Z^3$. Take for instance, take the convex hulls $$ \begin{align*} &\...
1
vote
0answers
21 views

Partition of polytope (with respect to convex hull)

Let's assume a given (convex) polytope P. There are a number of papers regarding partitions, but I couldn't find a starting point for my problem: I'm looking at a partition of P into polytopes P_i ...
3
votes
0answers
55 views

What polyhedron has the highest surface area to price ratio for tea bags?

I recently purchased tea where the tea bags were oddly tetrahedron-shaped rather than the common square tea bag shape. My girlfriend told me that the tetrahedron shape maximizes surface area, compared ...
0
votes
1answer
23 views

Detecting weakly redundant constraints of a Convex Polytope

I am currently dealing with a problem where I need to detect all redundant constraints of a convex polytope defined by $\mathcal{P} = \{x\in\mathcal{R}^n: Ax\leq b \wedge Cx = d \}$, basically your ...
0
votes
0answers
18 views

Calculating the measure of the intersection of generally positioned $n$-orthotopes (hyperrectangles) from their vertices

If I have a collection of $n$-orthotopes (hyperrectangles) for which the vertices are given as vectors in $\mathbb{R}^n$, how do I calculate the measure (or, let's call it volume or hypervolume) of ...
1
vote
1answer
34 views

Existence of an inner point in a nonempty polyhedron

I was reading some notes on polyhedral analysis and encountered a proof that confused me. The proof is in the book named "Integer and Combinatorial Optimization" by Wolsey and Nemhauser. Let ...
1
vote
0answers
14 views

Brute-force vertex enumeration for polytope

Let $P$ be a polytope of $\mathbb{R}^n$ defined by a (bounded) finite family of half-spaces $t_i \cdot x \leq q_i$ with every $t_i \in \mathbb{R}^n$ non-zero and $q \in \mathbb{R}$. There is no ...
0
votes
0answers
14 views

Criterion for polytope being full-dimensional using bounding hyperplanes

Suppose $P$ is a polytope of $\mathbb{R}^n$ defined by a (bounded) finite family of half-spaces $t_i \cdot x \leq q_i$ with every $t_i \in \mathbb{R}^n$ non-zero and $q \in \mathbb{R}$. Let $V \...
1
vote
0answers
40 views

Cyclic $d$-polytope — does every facet border every other facet?

A cyclic $d$-polytope is "neighborly," where every set of vertices sized $d/2$ together make up a face. What I'm interested in: in a cyclic $d$-polytope with $N$ facet ($d-1$ dimensional ...
1
vote
2answers
42 views

Having trouble understanding difference between polyhedron and polytope

Hi i´m reading a pdf about linear programming and i´m having trouble understanding the difference between a polyhedron and polytope between those two definitions A polyhedron P ⊆ $R^{n}$ is the set ...
1
vote
0answers
30 views

An example of polytope with exponential number of vertices?

I am looking for an example of polytope with exponential number of vertices? (Like $2^n$ vertices) I guess that dual of cyclic polytopes has exponential number of vertices. Are there simpler & ...
0
votes
1answer
34 views

Intersection of a straight line and a convex polytope

I apoligize in advance if the question might appear trivial, but there is something unclear to me related to convex polytopes in high dimensions. Let $P$ be a convex polytope in $\mathbb{R}^d$ for $d\...
0
votes
0answers
11 views

Show that the convex hull of vertices of polytope is the same polytope

I know there are many equivalent definitions in this field, so I will define all the properties by the way I studied them, and you can go only from these definitions: I define a polytope - bounded ...
3
votes
0answers
33 views

Generalisation of spanning tree in simplex

Let $\Delta$ be some $n$-simplex. Note that if some $n-1$-dimensional affine hyperplane $U$ intersects $\Delta$, then $U$ separates the vertices of $\Delta$. Therefore, if $T$ is some spanning tree of ...
1
vote
0answers
70 views

What do I need to prove here?

I found this question but I think I don't understand the question properly. The author asks to describe (in coordinates) the faces of the intersection of a cube $C$ of $r$-dimensions, $C=\{0\leq p_{s}\...
0
votes
0answers
32 views

Determine whether $S_1=\{{x\in{R^2}}\mid |x_1|+|x_2|\le 1\},S_2=\{{x\in{R^2}}\mid |x_1|+|x_2|\ge 1\}$ are polyhedral.

Determine whether $$S_1=\{{x\in{R^2}} \mid |x_1|+|x_2|\le 1\} $$ $$S_2=\{{x\in{R^2}} \mid |x_1|+|x_2|\ge 1\} $$ are polyhedral. The definition of polyhedron is that $S =\{{x\in{R^n}} \mid Ax\ge b\} $,...
2
votes
1answer
46 views

Can each edge of a Wythoffian polytope be flipped by a reflection?

A Wythoffian polytope $P\subset\Bbb R^d$ is an orbit polytope of a finite reflection group, that is, $$P:=\mathrm{Orb}(\Gamma,x):=\mathrm{conv}\{Tx\mid T\in\Gamma\},$$ where $\Gamma$ is a finite ...
1
vote
1answer
62 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

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 ...
1
vote
1answer
59 views

Proving that a $3$-dimensional compact polytope such that every two vertices are adjacent is a tetrahedron

So I have to prove that given a 3-dimensional compact polytope such that every two vertices are adjacent, then it is a tetrahedron. Somehow I'm able to visualise from the fact that every two vertices ...
3
votes
0answers
28 views

Relation of vertices of polytopes

Consider the convex polytope $$P=\{x\in\mathbb R^n:Ax\leq b, x\geq 0\}$$ for a matrix $A\in\mathbb R^{m\times n}$ and $b\in\mathbb R^m$. Motivated by the usual procedure of transforming a polytope ...
1
vote
1answer
60 views

Intersection of polytopes

Given two polytopes, $\mathcal{S}$ and $\mathcal{U}$, they can be described as the intersection of finitely many halfspaces, i.e., $\mathcal{S} := \{x \in \mathbb{R}^n \mid A x \leq b \}$ and $\...
1
vote
1answer
34 views

Intersection of a pointed cone and a hyperplane is a polytope?

Let $C = \text{cone}(u_1,\dots,u_m)$ for some $u_1,\dots,u_m \in \mathbb{R}^d \setminus \{\textbf{0}\}$ be a finitely generated pointed cone. Let $H_0 := \{x \in \mathbb{R}^d: \langle a,x \rangle = 0\}...
0
votes
1answer
44 views

Convex hull of points

We're studying a course and we're dabbling a bit in convex optimization. We were told that the convex hull of a set of points x1,..,xn is a polytope and we were ...
5
votes
1answer
47 views

Why does the cube have the fewest facets among (centrally) symmetric polytopes in $\mathbb{R}^n$?

"A body like the cube, which is bounded by a finite number of flat facets, is called a polytope. Among symmetric polytopes, the cube has the fewest possible facets, namely $2n$." I am ...
2
votes
2answers
53 views

Let $P$ be a polytope of dimension $d$. Then for some $v \notin$ aff($P$), the pyramid $v \ast P$ has dimension $d+1$.

Let $P$ be a polytope of dimension $d$. Then for some $v \notin$ aff($P$), the pyramid $v \ast P$ has dimension $d+1$. I’m looking for a straightforward argument to prove this statement. All the ...
3
votes
0answers
24 views

4d projection of 5-cube [duplicate]

The vertex-first parallel projection of the tesseract into three-dimensional space has a rhombic dodecahedral envelope. What is the four-dimensional projection of the five-cube? By analogy, its ...
1
vote
3answers
86 views

What are the extreme points of this polytope?

Let $n, k$ be positive integers with $n\geq k$. Let $P_{n,k}$ be the set of vectors $x$ in $[0,1]^n$ for which $$ \sum_{i=1}^n x_i = k $$ $P_{n,k}$ is defined by linear equations, so it is a polytope. ...
0
votes
1answer
51 views

Clustering of vertices in an n dimensional cube

Consider the vertices of an n-dimensional cube. Distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices. If we call ...
0
votes
1answer
77 views

Dual of 7 dimensional regular simplex [closed]

I have the vertices of a 7-simplex that can be inscribed in a 7-cube. Given this information, how can I find the vertices of its dual simplex? (Note that the vertices of this dual should be the ...
1
vote
0answers
98 views

Measurements on 7 dimensional cube

For a particular problem, I think I've found a way to solve it by translating it into a 7-dimensional cube. Basically, I'll associate the vertices of the cube with some objects and would have to find ...
0
votes
0answers
21 views

Characterization of conjugate faces of mutually polar convex sets

This is exercise 6.6 in Arne Brondsted's "Introduction to Convex Polytopes": Let C and D be mutually polar compact convex sets. Let F be a proper exposed face of C and let $G = F^\triangle$...
0
votes
0answers
20 views

How to find a projecting of a point into the intersection of semi-spaces? [duplicate]

I have a point $A\in\mathbb{R}^n$ and a set of $k$ constraints of the form $$a_i + \alpha a_j+ \geq \epsilon$$ for $\epsilon>0$ and $a_i$ the $i$ dimension of $A$. How can I find the projection of ...
1
vote
4answers
40 views

Number of Zonotope Edges Parallel to Generator

Suppose we have a zonotope $Z$ that is the Minkowski sum of line segments $U_1+\dots +U_n$. All the edges of $Z$ are parallel to some $U_i$. Is it also true that the number of edges parallel to $U_i$ ...
1
vote
1answer
63 views

How to generate vertex-transitive tilings?

It is trivial to construct vertex-transitive polytopes: choose any finite matrix group $\Gamma\subseteq\mathrm O(\Bbb R^d)$ and some point $v\in\Bbb R^d$. Take the convex hull of the orbit $\Gamma v$, ...
1
vote
1answer
31 views

Upper Bound Theorem for Simplicial Spheres

I am recently approaching combinatorial commutative algebra and I am studing Upper Bound Theorem for Simplicial Spheres (Stanley 1975). My question is so a bit general and maybe ingenuous... Momentum ...
0
votes
0answers
19 views

Set of hyperplanes through vertex of cube

Let $K \equiv [0,1]^n$. Fix any vertex $X$ of $K$. My question is: What is the set of gradients of hyperplanes passing through $X$ which have non-empty intersection with the interior of $K$ (i.e. ...
-1
votes
1answer
46 views

How to determine the number of the faces of a 4-dimensional polytope?

Determine the number of 1, 2 and 3-dimensional faces of the polytope $$S= conv \{(\pm 1, \pm 1, 0, 0), (0,0, \pm 1, \pm 1)\}$$ (the convex hull of 8 points in $\mathbb{R}^4$). I've been struggling ...
0
votes
0answers
17 views

Linear programming: Range of subgradients of linear functions maximized at a point

Consider any non-empty compact convex feasible set defined by linear inequalities in $\mathbb{R}^n$. Clearly, this feasible set is a convex polytope, say $P = \{x \in [0,1]^n: A_i^T x \geq0, B_j^T x = ...
1
vote
0answers
54 views

Question Regarding Complete Normal Fans and Duality

I have a question regarding the definition of a normal fan. The definition is thus: "Given a non-empty polytope $P \subset \mathbb{R ^d}$, the normal fan $N(P)$ of $P$ is the fan consisting of, ...
4
votes
1answer
69 views

Is a pyramid uniquely determined by its edge-lengths?

I am looking for a nice/short proof of the following: The shape of a pyramid with a convex polygonal base is already uniquely determined by knowing the length of all its edges. By "knowing the ...
1
vote
0answers
28 views

Two antipodes, one overarching algebra? (Two compositional inversion formulas)

The rows of the lower triangular matrix of Narayana numbers are the coefficients of the h-polynomials of the Loday-Stasheff associahedra and are related to the coarse f-polynomials of the associahedra ...
1
vote
2answers
29 views

Which convex deltahedra are inscribable in the sphere?

A convex deltahedron in $\mathbb{R}^3$ is a convex polyhedron whose faces are all equilateral triangles. There exist precisely 8 convex deltahedra. Some examples are the regular tetrahedron, the ...
2
votes
1answer
59 views

How to algebraically (without graphing) find coordinates delimiting the solution region of a system of linear inequalities?

I would like to know how to algebraically (without graphing) find coordinates delimiting the solution region of a system of linear inequalities. For example: $$ \left\{ \begin{array}{c} x\ge2 \\ y\...
0
votes
2answers
27 views

If the polytope is unbounded then there is no optimal solution

Show if true or a counterexample if false a) If the feasible polytope described by the solution space of a linear programming problem is unbounded then there is no optimal solution b) If there are two ...
1
vote
2answers
115 views

Extreme points of polytopes

Let $F$ be a convex bounded polytope in $\mathbb{R}^N$. Let $S$ be a linear subspace of $\mathbb{R}^N$ defined as $S=\{x \in \mathbb{R}^N: Ax = \vec{0}\}$, where $A$ is an $m \times N$ matrix, $0 \leq ...
1
vote
1answer
40 views

Is there 4-polytope with rhombic dodecahedron cells?

I'm not as mathy as I wish I were, so wrt the advice stackexchange just presented me with: to "explain what I don't know," I'm afraid that's a rather long list, stretching deep into the &...
0
votes
0answers
31 views

Question about lower convex hull of a polytope

Question about lower convex hull of a polytope. Consider the pyramid with triangular $black$ face as the base of the pyramid. This is a polytope constructed of $4$ coordinate points ($3$ at the plane ...

1
2 3 4 5
12