Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [polytopes]

In elementary geometry, a polytope is a geometric object with flat sides, and may exist in any general number of dimensions n as an n-dimensional polytope or n-polytope. (Def: http://en.m.wikipedia.org/wiki/Polytope)

3
votes
0answers
37 views

Why is the permutohedron simple?

I am working with the permutohedron in $\mathbb{R}^n$ which is defined as follows: $$\Pi_n := conv\{(\sigma(1), \ldots, \sigma(n))\ |\ \sigma \text{ permutation of } [n]\}$$ I want to show that this ...
1
vote
2answers
43 views

Elementary proposition on triangulations

I have a question on triangulations. Let T be a triangulation of a d-dimensional cross-polytope. Let s be a (d-1)simplex that does not lie on the boundary of the cross-polytope. How can we show that ...
0
votes
0answers
26 views

Products of k/l-gons

For $k \geq 3$ let $P_k = conv\{(\cos\frac{2\pi\cdot i}{k}, \sin\frac{2\pi\cdot i}{k})\ |\ 0 \leq k < i\}$ be a regular $k$-gon in $\mathbb{R}^2$. We want to look at product $P_k \times P_l$ in $\...
1
vote
1answer
44 views

Projective Transformation for two distinct vertices and a linear objective function

I am trying to understand how to prove the following, which seems to be a quite useful insight in terms of linear optimization. Unfortunately, I have a hard time with projective geometry. I'd greatly ...
1
vote
1answer
49 views

Help me to calculate polyhedron area or let me know the references about it.

I'm a student who is studying the Management Science in the Republic of Korea. I'm looking for a reference to calculate the area of the system of inequalities. I can easily calculate when the number ...
0
votes
0answers
29 views

Convex hull of {-1, 1} rank-1 matrices?

Consider set $\mathbb{R}^{m\times n}$ of $m \times n$ matrices. I'm particularly interested in properties of polytope $P$ defined as a convex hull of all {-1,1} matrices of rank 1, that is, $$ P = \...
2
votes
1answer
34 views

Number of facets of the Birkhoff polytopes $B(n)$.

The wikipedia's page for Birkhoff polytope states that the polytope has $n^2$ facets, determined by the inequalities $x_{ij} \geq 0$, for $1 \leq i,j \leq n$. I've tried different things but can't see ...
0
votes
1answer
18 views

Given two polytopes $P$ and $Q$, show that $(P^* \times Q^*)^* = P \oplus Q $

Using definitions, I got so far as to express $(P^* \times Q^*)^*$ in the following form: $$(P^* \times Q^*)^* = \left\{\,\begin{pmatrix} z^* \\ w^* \end{pmatrix} \in \mathbb{R}^{d+e} \,\middle|\,...
1
vote
2answers
58 views

Can anyone tell me the name of my shape?

I'm trying to optimize something over the region in the positive octant of R^3 defined by: ...
0
votes
1answer
26 views

Request for verification of the technique for deducing vertices of a polytope

I am trying to find the vertices of a polytope which is defined by two parallel planes of the form ${\bf{a}^T\bf{w}}=c_1, {\bf{a}^T\bf{w}}=c_2$, where $\bf{a}\in \mathbb{R}^n_+, \bf{w}\in \mathbb{R}^...
1
vote
1answer
61 views

Finding vertices of a polytope with a given set of inequalities.

I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, and a set of bounds for the coordinates: $v_k\in[0,a_k],\ 1\le k\le n$, where $a_1\ge a_2\ge \cdots\ge a_n\ge 0$. My question is: ...
0
votes
1answer
30 views

Show that each edge of the cyclic polytope $C_4(6)$ is contained in either three or four facets, and either three or four 2-faces.

Note: here $C_4(6)$ is the notation for the cyclic polytope of dimension 4 and of 6 vertices. By the 2-neighbourly property of $C_4(6)$ and the Dehn-Sommerville equations, I've determined that the ...
1
vote
0answers
29 views

Polytope: from $\mathcal H$-representation to $\mathcal V$-representation

This question nicely explains how to go from a vertex representation ($\mathcal{V}$) to a half-space representation ($\mathcal{H}$) of a polytope. But I don't fully understand how to go from a half-...
0
votes
1answer
24 views

How to find an extreme feasible point in a linear polytope (set $\{x : Ax \leq b\}$ defined by halfspaces)?

The set $$\mathcal P = \{x : Ax \leq b\}$$ is a linear polytope (or, more precisely, an $H$-polytope) and is defined as the intersection of a finite number of halfspaces. The simplex method for the ...
7
votes
0answers
56 views

Can a regular $n$-simplex have vertices in $\mathbb Z^n$ for $n > 1$?

Trivially, a regular $0$-simplex (point) and $1$-simplex (line segment) can have integer vertices in $0$ and $1$ dimensional Euclidean space respectively. On the other hand, a regular $2$-simplex (...
2
votes
1answer
58 views

Algorithms for projecting a point onto the convex hull spanned by a set of vectors

Given a set of vectors $V = \{ \mathbf{v}_1, \ldots, \mathbf{v}_n \} \subset \mathbb{R}^d$, I want to project a point $\mathbf{x}_0 \in \mathbb{R}^d$ onto the convex hull $\text{conv}(V)$ of the ...
0
votes
0answers
52 views

Gale's evenness condition applied to cyclic polytopes and simplices

Please give your comment on the following problem. In our class we use the following definitions and the following version of the Gale's evenness condition. My analysis of part a is that, the graph $...
1
vote
0answers
75 views

Decomposing a polyhedron in $\mathbb{R}^3$ into a lineality space, cone, and polytope.

Consider the set in $\mathbb{R}^3$ given by $$\{(x,y,z) : x+y+z\ge 3, x \ge 0\}$$ I can picture this set; it is simply the intersection of two half-spaces. A theorem states that every polyhedron can ...
0
votes
3answers
25 views

3-polytope with 9 vertices and 8 facets

My guess is that this is a 3-polytope, since the existence of the two facets {357} and {048} rules out the possibility of dimensionality 2 and 4. How can I go about sketching it?
2
votes
0answers
19 views

Is there a systematic approach of showing that a given set is contained in a given convex polytope?

Let us assume that we are given a set $S=\{x\in \mathbb{R}^n:h(x)\le 0\}$, and we are given a set of points $p_1,\cdots,\ p_{n+1}$, such that $p_i\in S$. My question is: Is there a systematic way ...
1
vote
1answer
29 views

Permutahedron of three vectors (1,1,0,0), (−1,1,0,0), (−1,−1,0,0).

I'm getting stuck on parts b, c, and d. Since visualizing the polytope is not possible, I think the way to find the facets and edges of P is to determine which combinations of points form facets and ...
5
votes
2answers
43 views

How many uniform polytopes are there in higher dimensions?

I am not really interested in the exact numbers, but more in the richness of the class of uniform (convex) polytopes in higher dimensions. Wikipedia contains the followin statement: In five and ...
3
votes
3answers
167 views

Product of two polytopes is a polytope

Please have a look at my attempt for this problem. Let $x = \begin{pmatrix} x_1\\ x_2 \\ \end{pmatrix}, x_1 \in P_1, x_2 \in P_2$. I want to show that $x \in conv\{P_1 \times P_2\}$, i.e. $x$ can be ...
3
votes
1answer
54 views

Does there exist a higher-dimensional 5-sided “tetrahedron + 1”?

The first shape is "0"-sided and is a point. The next shape is a line segment and it's "1"-sided. The next shape is a triangle and it's 3-sided. The next shape is a tetrahedron and it's 4-sided. ...
0
votes
1answer
17 views

Definition of centrally symmetric polytopes

I'm doing this exercise and have trouble with the definition of centrally symmetric polytopes. I understand what it means, but it just doesn't look like a workable definition in solving this problem. ...
1
vote
1answer
71 views

What is the term to use for 1-dimensional polytope?

I am assuming that a polygon is defined as a 2-dimensional polytope. In that case, a 1-dimensional polytope will be a connected union of line segments. In other words, it is a physical realization ...
1
vote
0answers
71 views

The idea behind Delzant construction of a toric manifold from a convex polytope

I am trying to understand how to visualize a symplectic toric manifold from its moment polytope, following chapter 29.4 in "Lectures on Symplectic Geometry" by Ana Cannas da Silva: https://people.math....
3
votes
1answer
56 views

Why can't a vertex of a $d$-dimensional polytope be in fewer than $d$ edges?

This is motivated by the definition of simple polytopes: if all vertices of a $d$-dimensional convex polytope $P$ are in exactly $d$ edges (i.e. $1$-dimensional faces of $P$), then $P$ is simple. I ...
2
votes
0answers
44 views

Smooth function from $\mathbb R^n$ to a polytope

Given an open bounded convex polytope $C$ in $\mathbb{R}^n$, is there a way to construct a smooth function from $\mathbb{R}^m$ to $\mathbb{R}^n$ whose image is $C$? For instance, if $C$ is the unit ...
0
votes
0answers
35 views

How to compute the image of a polytope after a linear transformation (formal proof) ?

I have been looking for a result with (formal proof) of the following question (exactly the same question as posed in https://mathoverflow.net/questions/179282/mathcalh-polyhedron-under-a-linear-map?...
0
votes
1answer
45 views

Is the solution set of a linear program always bounded?

Let $$\max\left\{c^T \cdot x \mid A \cdot x \leq b, x \geq 0\right\}$$ be an arbitrary linear program and let $M$ be its solution set. Is $M$ always bounded? I think the solution set of linear ...
0
votes
0answers
43 views

Projection of convex polytope onto plane

A convex polytope is given by a system of linear inequalities in 4D space. How do I find its projection onto plane given by equation $x_1 + x_2 = 0$? If it was $x_1 = 0$, I'd use Fourier-Motzkin ...
1
vote
1answer
50 views

Prove that the polar set of a convex set contains the origin

Let the polytope $P = \text{conv}\{p_1,\ldots,p_N\} \subset \mathbb{R}^n$ and the polar set defined by $$Q = \{x\in \mathbb{R}^n : p_i^Tx \le 1, \forall i \in \{1,\ldots,N\}\}.$$ Prove that the origin ...
0
votes
1answer
15 views

How to compute the vertices of a hypercube given in H-form

I am working with a hypercube given in H-form: {x: Vx <= 1}. How would I compute the vertices of this hypercube?
0
votes
0answers
36 views

The meaning of the dimension of a Newton polytope

I am not very familar with algebraic geometry. Thus, maybe my question is a really basic one, but I have not find an answer in literature. I consider Newton polytopes of multivariate polynomials $f(x)...
0
votes
1answer
43 views

Number of vertices of a partiuclar polytope

Question: I would like to know the number (or a good approximation of it) of vertices of the polytope arising from the following constraints: $\{ (a_{1,1},\ldots,a_{1,n}, a_{2,1}, \ldots a_{2,n},\...
0
votes
0answers
44 views

computing polynomials whose roots are the vertices of 4-polytopes of circumradius one interpreted as quaternions

Suppose we have the vertices of 4-polytopes which have been scaled so that their are on the unit sphere. Interpret them as quaternions. If these have been computed before, I'm looking for a ...
0
votes
1answer
26 views

Consider a simple convex polyhedron, determine the vertices

Consider a simple convex polyhedron Δ in ℝ𝟛 with 2013 faces. How many vertices are there in Δ ? How many of the vertices have index one with respect to linear function?(not equal to a constant on ...
1
vote
0answers
67 views

Algorithm for Union of Polychora (4D Polytopes)

In the course of my research (radio engineering), I need to solve the following problem, for which I do not feel well equipped. I would like to calculate the union of polychora (4-polytopes, bounded ...
0
votes
0answers
25 views

Mean width distance and containment of ball

Let $B_n$ denote the Euclidean unit ball in $\Bbb R^n$, and let $P\subset B_n$ be a polytope such that $w(B_n)-w(P) \leq \epsilon$, where $w(K)=2\int_{\Bbb S^{n-1}} h_K(u)\,d\sigma(u)$ is the mean ...
1
vote
0answers
23 views

Procedure to generate 2-dimensional convex polytopes with a given number of vertices

I need to deal with the following. Let $[B]$ denote the set of integers $\{0,1,\ldots,B\}$. Consider an integer $n \geq 3$ and a grid $[B]\times [B]$, and let $P_{n,B}$ denote the set of convex ...
1
vote
0answers
66 views

Can one induce the Dual Subdivision of Tropical Signomials Similarly to Tropical Polynomials?

Preliminaries. Consider the semiring $\mathbb{T} = \{\mathbb{R} \cup \{-\infty\}, \oplus, \odot \}$, where the $a \oplus b = \max\{a,b\}$ and that $a \odot b = a + b$. The addition and scalar ...
0
votes
1answer
32 views

Why does a d-polytope being k-neighborly for 1 <= k <= d imply the polytope is neighborly for all k' such that 1 <= k' <= k?

I'm reading Grunbaum's Convex Polytopes where he cites the following theorem in a proof by contradiction for a larger theorem: "If $P$ is a $k$-neighborly $d$-polytope, and if $1 \le k' \le k$, ...
1
vote
0answers
24 views

Sampling extreme points from Minkowski Sum

I recently stumbled upon the following subproblem: we are given zonotopes $P_1, \dots, P_m$ in $\mathcal{V}$ representation (i.e. we are given the extreme points of each $P_i$). Denote the Minkowski ...
0
votes
1answer
38 views

Proving full rank of a special type of a (0,1,2)-integer matrices

My question arise at the consideration of Newton polytopes. In that context I consider integer matrices $ A =(a_{ij})\in \mathbb{Z}^{(n+1) \times N} $ with $n+1 \leq N$ having the following ...
0
votes
1answer
24 views

Is there a specific name for polytopes that only have 0s and 1s as coordinates?

I only know of the name 0/1-polytope, but whenever I search for it on Google, I get articles written by the same author. So I think there is another name for it.
-3
votes
1answer
182 views

Are the corner hypercubera polytopes self-dual?

Motivation: The polyhedron whose vertices are seven of the vertices of a cube (four on the bottom and three on top) - called a cubera - is self-dual. Does an analogous construction produce a self-dual ...
2
votes
1answer
144 views

How to algorithmically find only the edges of a high dimensional convex hull?

Given to me is a set of points $p_1,...,p_n\in\Bbb R^d$ in general position. I want to determine only the edges of the convex hull $C:=\mathrm{conv}\{p_1,...,p_n\}$, and this as efficient as possible. ...
1
vote
1answer
69 views

In what sense are “projecting” and “taking sections” of polytopes dual operations?

It seems to be folklore that projecting and taking sections of polytopes are somehow "dual operations" (e.g. explicitly noted in the abstract of this paper, or suggested by this answer to an MO ...
7
votes
0answers
61 views

Is this construction of the “edge polytope” known?

Given a convex polytope $P\subseteq\Bbb R^d$. I am going to construct a new polytope from its edges (I call it the edge polytope) with the following steps: Take the 1-skeleton of $P$. Extract the ...