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

0
votes
0answers
25 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
21 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
13 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
65 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
34 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
18 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
11 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
6 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
13 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
88 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
12 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
49 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
41 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
91 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
45 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
10 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
32 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
71 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
46 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
25 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
85 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
69 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
25 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
45 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
22 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
25 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
32 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
12 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
48 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 ...
1
vote
0answers
13 views

competing definitions for polytope dual

Along with a polytope P one has the notion of its dual which is officially defined via the inner product. However, in three dimensions at least, the dual is often pictured simply by placing a point ...
1
vote
1answer
40 views

On a convex polytope

Let $e_i$-s denote the standard unit vectors of $\mathbb{R}^n.$ Denote $$\mathcal{C}_k = \left\{ \sum_{i \in S} \pm e_i \colon S \subseteq \{ 1,2,..., n\} \mbox{ and } |S| \leq k \right\}$$ the set ...
1
vote
0answers
41 views

Simplicial polytope Dehn-Sommerville Equations

Let's suppose we have a polytope P with $dim(P)=d$ and the h vector $ h(P,x)=\sum\limits_{i = 0}^{n} h_ix^{d-i}$ i have to prove that if $h_{k}=h_{d-k}$(simplicial polytope) then $xh(P,x)=h(P,1/x)$ ...
1
vote
0answers
28 views

The polytope of ways to express an interior point of a polytope as an average of the vertices

If a convex polytope in $\mathbb R^n$ has more than $n+1$ vertices, then each point in its interior is a convex combination of the vertices in more than one way. For each interior point, the set of ...
0
votes
1answer
21 views

Facets shared by two points on a convex polytope

I have a convex polytope of arbitrary dimension. Let $\mathcal{F} (A)$ denote the set of facets that vertex $A$ belongs to. If two vertices share an edge, is it true that the disunion of $\mathcal{F} (...
0
votes
0answers
146 views

Projection of hybercube without Fourier-Motzkin 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 ...