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)

learn more… | top users | synonyms

1
vote
1answer
13 views

Nichtnegativstellensatz the same as Handelman's Theorem?

Wikipedia on "Handelman's theorem: If $K$ is a compact polytope in Euclidean $d$-space, defined by linear inequalities $g_i ≥ 0$, and if $f$ is a polynomial in $d$ variables that is positive on $K$, ...
3
votes
0answers
24 views

Handelman's Theorem on Nonnegative polynomial in Compact Polytope?

Background: Representing polynomials by positive linear functions on compact convex polyhedra by David Handelman Consider a polynomial $f\in K[x_1,\ldots,x_n]$ in a compact polytope, related ...
2
votes
1answer
37 views

Bounds on Hausdorff distance via singular values

For some $\delta>0$, let $X$ and $X_\delta$ be two bounded convex polytopes in $\mathbb{R}^n$, defined as $X = \{x \in \mathbb{R}^n : Ax \leq b \}$ and $X_\delta = \{x \in \mathbb{R}^n : Ax \leq b +...
1
vote
1answer
39 views

Prioritized solution of a linear system subject to inequality constraints

Consider the following linear system \begin{equation} y = A_1 x_1 + A_2 x_2 \end{equation} subject to the linear constrains \begin{equation} C_1 x_1 + C_2 x_2 \leq d \end{equation} I am looking ...
0
votes
1answer
39 views

Convex compact set must have extreme points

I am reading a paper and there is such description as title. Why? I have an example: $(0,1)$. This is a convex set but not closed, so I cannot find an extreme point. However if convex and compact,...
1
vote
0answers
16 views

Convex 4-polytopes requiring 6 or more colors

Projected into 3-D space, a convex 4-polytope looks like a collection of convex polyhedra. If any two convex cells sharing a face have different colors, how many colors are required? In the paper ...
0
votes
0answers
26 views

Maximum length of a ray shot from an interior point of a polytope?

assume that I have a polytope $\bf{Ax \le b}$ and I also have an interior point corresponding to the nominal values of x, namely $\bf{x^0}$. Given a weight w for each dimension (coming from uniform ...
0
votes
0answers
29 views

Solutions to Diophantine Moving Window Inequations

I am interested in finding the number of non-negative integer solutions, $N(m,h,u)$, to this system of inequations $$ \left\{ \matrix{ 0 \le x_{\,0} + x_{\,1} + \cdots + x_{\,m} \le u \hfill \...
2
votes
0answers
16 views

For the n^th dimension, where n is ≥5, there exists only 3 regular convex polytopes proof

A lot of books stated that is true, however, no proof is given. I was wondering if anyone could help me and show me a proof? Statement: For the n-th dimension, where n is ≥5, there exists only 3 ...
1
vote
1answer
66 views

3-dimensional measure of a permutahedron

Let $P = \operatorname{conv}\lbrace (s(1), s(2), s(3), s(4)) \mid s \in S_4 \rbrace$ be a permutahedron. Compute the 3-dimensional measure of this polytope. I know that $P$ is three dimensional (...
1
vote
0answers
37 views

Approximating Minkowski Sum of 3 dimensional Convex Polytopes by Sampling

Let $P_1,P_2...P_r$ be a set of convex polytopes with $n_r$ vertices in 3 dimensions. These polytopes basically represent uncertainties of '$r$' number of 3d-points respectively in space. The global ...
1
vote
0answers
19 views

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

This MO answer on enumerative geometry details the sense in which an associahedron is a product of lower dimensional associahedra and the comments in this MSE-Q indicate the same is true for ...
1
vote
0answers
9 views

How does this alternative formulation of an hyperplane work?

I am studying 0/1 polytopes from Ziegler's lectures on polytopes https://arxiv.org/pdf/math/9909177.pdf. I found a small part of a proof of a corollary, which I do not understand. Here it is (...
0
votes
1answer
19 views

Projective Geometry: Combinatorially, but not projectively equivalent polytopes

I have a hard time understanding Projective Geometry. My task is to Find two polytopes, that are combinatorially, but not projectively equivalent. What combinatorially equivalent means is ...
0
votes
0answers
13 views

Alternate proof that the intersection of half spaces associated to facets of a cone, is that cone

Let $\sigma$ be a convex polyhedral cone and $V$ be span ($\sigma$). Then associated to any facet $\tau$ of $\sigma$ there is a unique $u_\tau$ up to scalar multiplication such that $Ann \, u_\tau \...
0
votes
0answers
4 views

Minimum Cost Flow Polytope Facets

When solving the minimum cost flow problem you can frame it as a linear program as shown in the Wikipedia article here. So, the set of vectors $f : V \times V \rightarrow \mathbb{R}$ which satisfy the ...
0
votes
0answers
8 views

Polytope $P':=\text{conv}\{P\cup \{v'\}\}$ obtained by removing a vertex and replacing it with a vertex “beyond”

Definitions and properties Let $P$ be a convex polytope. A half-space $H^{\le}:=\{x\in\mathbb{R}^{d}\mid c^{T}x\le y,\, c\in\mathbb{R}^{d}\}$ associated with an hyperplane $H=H^{=}=\{x\in\mathbb{R}^{...
1
vote
0answers
15 views

Proof that for any face $F\neq P$ of a convex polytope is contained in a face OF dimension $\text{dim} F+1$.

Consider a convex polytope $P$ in $\mathbb{R}^{d}$ as the convex hull of a minimal finite set $V$ whose elements are called "vertices", or equivalently as the bounded intersection of a finite ...
8
votes
1answer
90 views

can a convex polygon have only one boundary point at locally maximum distance from its centroid?

It's easy to see that given any convex polygon P and any point c in its interior, there is at least one point m on the boundary of P at locally maximum distance from c: simply choose m to be a vertex ...
0
votes
0answers
16 views

Why calculating the volume of Birkhoff polytope is complicated?

It is known that, Calculating the volume of Birkhoff polytope in higher dimension is still open. I am not very good on it, trying to understand, why it is complicated? It would be really great if ...
0
votes
0answers
13 views

Dual of cartesian product of duals of polytopes

I am working on the following problem. Let $P\subseteq \mathbb{R}^d, Q\subseteq \mathbb{R}^e$ be full-dimensional polytopes, both with the origin in the interior. Describe $(P^{\circ }\times Q^...
2
votes
1answer
54 views

Real world uses or interesting facts about/for Associahedron or Permutohedron

I'm doing a small research project into these but their Wiki page and other pages I've looked at just detail what they are, and their properties. Does anyone know of any real world applications or ...
0
votes
0answers
15 views

Have people studied these polytopes?

Given a rational polytope $Q \subset \mathbb{R}^n$ we may define a family of integral polytopes in the following fashion. Let $\overline{Q_i}:=convexHull(iQ \cap \mathbb Z^n)$ So I imagine taking $Q$...
0
votes
0answers
7 views

Building a convex set out of two convex sets where each extremal point of one set shares and edge with each extremal point of the other [duplicate]

Consider a convex set $P$ with two faces $f_1, f_2$ s.t. all extreme points of the convex set belong to either $f_1$ or $f_2$ (but none blong to both - the two faces are disjoint in the set of ...
0
votes
0answers
16 views

How do I prove this simple result for the face structure of convex sets?

I have a convex set $P$ with faces $f_1, f_2$ such that all extremal points of the convex set belong to either $f_1$ or $f_2$ (the faces are disjoint and cover $P$). How can I prove that if every ...
0
votes
0answers
18 views

Points on the moment curve form the vertices of the corresponding cyclic polytope

Working through Matousek and I am stuck on exercise 5.4/1a Show that if V is a finite subset of the moment curve, then all the points of V are extreme in conv(V); that is, they are vertices of the ...
0
votes
1answer
44 views

Scissor equivalence/congruence of two convex hulls

Is the convex hull in $\mathbb{R}^2$ of $\Bigg\{\begin{pmatrix}0\\0\end{pmatrix}, \begin{pmatrix}3\\0\end{pmatrix}, \begin{pmatrix}0\\1\end{pmatrix}\Bigg\}$ scissor equivalent/congruent to the convex ...
4
votes
1answer
99 views

Extreme points of intersection of the orthant (quadrant) with an Hyperplane in finite dimension vectorial space

Note : Having spent some time over the original problem below, I saw that it can be boiled down to a simpler problem. Here is that simpler problem : In a vectorial space (over $\mathbb{R}$) of ...
0
votes
0answers
10 views

Convert the Matching Polytope LP to Dual Program

For my course in discrete optimization I am studying about Polytopes and their dual programms. They state that the convex hull of Perfect Matchings in grahph $G=(V,E)$ is given by: $$ x\geq 0\\ x(\...
1
vote
0answers
46 views

Some Basic Properties of Tropical Amoebas

I am working through Sturmfels' new book on Tropical Geometry with another student, and we are stuck at a pretty important concept, namely the basic properties of amoebas. Let me reproduce a bit of ...
1
vote
0answers
12 views

Commuting intersection and projection of convex polytope

I have a convex polytope $P\in\mathbb{R}^{n+m}$. I denote coordinates of an element $p\in P$ by $p(k)$. I need to compute the intersection of this polytope with a subspace given by some number of ...
0
votes
0answers
36 views

An polynomial time algorithm to solve LP

Is there a polynomial time algorithm that gives the extreme point as output for which objective function is minimized/maximized ? I am not looking for any solution that minimizes/maximizes the ...
0
votes
0answers
76 views

Difference between invariant and contractive sets

I came across this particular notion of contractive sets. I know what an invariant set is, but can anyone explain what a contractive set is and the difference between invariant and contractive sets?
1
vote
1answer
53 views

Polyhedra vs Polytope

I am having a hard time understanding what is the main difference between a polyhedron and a polytope. Could anyone explain me what is the difference between these two structures?
2
votes
1answer
26 views

Are two halves of a convex polytope themselves convex?

Suppose I have an $n$-dimensional convex polytope $P$ which is the convex hull of some set of vertices $V$. Now suppose I take a hyperplane $T$ that intersects $P$ and slice $P$ into two parts: $P_1$, ...
2
votes
1answer
93 views

Intersection of the corners of a hypercube and a hyperplane

Consider the corners $c$ of a unit hypercube in $\mathbb{R}^n$ (for example in $\mathbb{R}^2$, $c = \{\{0,0\},\{1,0\},\{0,1\},\{1,1\}\}$) and a hyperplane $p \subseteq \mathbb{R}^{n-1}$ (for example ...
5
votes
0answers
71 views

Interesting cube subdivisions: what is going on here, and what are these polytopes?

I was messing around recently with a unit cube. If you draw vertices on the midpoint of each edge of the cube, then connect those points by new edges, you will form the wireframe of what I figured ...
2
votes
0answers
24 views

Triangulations of combinatorially equivalent polytopes

I am wondering which relation(s) there are between triangulations of combinatorially equivalent polytopes that use no new points: Let $P,Q$ be a $n$-polytopes such that their face lattices are ...
1
vote
0answers
20 views

is this sufficient to define a simplex?

I want to define a simplex based on the following properties A convex polytope All vertexes share an edge with all others For a given vertex $v_i$ the set of all facets that the vertex belongs to ...
0
votes
0answers
22 views

what is special about simplexes?

Is it true that the $d$-simplex is the only convex polytope such that All vertexes share an edge with all others, It is transitive under the action of a group?
1
vote
0answers
26 views

Projection of hyper-cubes via multiple variable elimination

I am not a mathematician but I do use some tools from geometry in robotics. So, I apologize if what I am writing here is not mathematically consistent but I really do need your help. I have a linear ...
0
votes
1answer
46 views

Polytopes defined by $x_i >=0, Ax = b$ are generic ? (Understanding simplex method)

Consider polytopes in $R^n$ defined by $x_i >= 0, Ax = b$, for $b > 0$. Assume $A$ is of full rank $r$ and $Ax=b$ has solutions. The following properties seems to be correct. I would be ...
0
votes
0answers
15 views

Shelling of a polytope

During line shelling of a convex polytope in d-dimension, it is easy to see that visible facets are shellable. In the same way non visible facets are also shellable. But while combining these two part,...
1
vote
0answers
19 views

Property of pairs of disjoint convex polytopes in $\mathbb{R}^n$

I am having trouble proving the following property. Maybe the result already exists, but I could not find anything on the topic. Proposition: Let $P_1$ and $P_2$ be two disjoint polytopes of $\...
0
votes
0answers
24 views

Most efficient way of transforming from V-representation to H-representation

What is an efficient way to transform from the v-representation of a convex hull (in terms of vertices) to its h-representation ($Ax \leq b$)?
0
votes
1answer
26 views

What are the combinatorial types of the facets of a MTBF?

This question is about Main Tridiagonal Birkhoff Faces (or MTBFs), defined in this question. (One goal of this question - to be addressed in a corollary question - is to establish that MTBFs ...
1
vote
1answer
36 views

Convex hull of union of polytopes in halfspace representation

Suppose I have two polytopes in $\mathbb{R}^n$ given in H-representation as $P_1: \{x | H_1 x\leq b_1 \}$ $P_2: \{x | H_2 x\leq b_2 \}$ My question is, if it is possible to efficiently (i.e., avoid ...
0
votes
1answer
13 views

convex polytopes where every vertex pairwise shares a facet

for arbitrary dimension, what are the convex polytopes such that all vertices share a facet of some dimension, which is not the top facet (the entire polytope), with all other vertices? One example is ...
0
votes
0answers
14 views

Affine hull of a linearly constrained set (convex polytope)

For any $A \in \{0,1\}^{m \times n}$ and $r \in \mathbb{R}^m_{>0}$ consider the set $S := \{x \in \mathbb{R}^n_{\geq 0} \ | \ A x = r\}$ of non-negative solutions to the linear system $Ax - r = 0$. ...
2
votes
1answer
51 views

Rotations of 4-Cubes

I have recently learned the orbit stabilizer theorem, and have encountered unexpected results pertaining to the rotations of a tesseract; I am curious if there is any intuition for this. A $4$-Cube ...