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)

2
votes
1answer
38 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
39 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
40 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
21 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
16 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
25 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
41 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
147 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
50 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
15 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
57 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
53 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
48 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
39 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
25 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
0answers
29 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
37 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
14 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
30 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
38 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
25 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
64 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
24 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
22 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
59 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
23 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
22 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.
-4
votes
1answer
162 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
112 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
57 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
59 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 ...
3
votes
0answers
46 views

What is known about these “transparent” polytopes?

I am looking for the name (if there is one), simple properties and possible literature for the following class of polytopes (by polytope I mean the convex hull of finitely man points in $\Bbb R^n,n\ge ...
1
vote
0answers
18 views

Number of facets intersecting a face of a non-simple polytope

Let $P$ be a non-simple polytope and $E$ a face of codimension $k$ with $\dim E \geq 1$. Is it always true that $E$ is an intersection of $k$ facets of $P$? When $P$ is simple, this is always true. (...
1
vote
1answer
51 views

Techniques for finding the edges of a 4-dimensional convex hull

I am looking for some techniques in general, but let's do it on a (for me relevent) example. I have a set of $n^2$ points $$p_{i,j}:=\frac1{\sqrt 2} \begin{pmatrix} \cos(2\pi i/n) \\ \sin(2\pi i/n) \\...
0
votes
0answers
35 views

Convex Hulls and maximizing volume

I thought of a function (recreational mathematics) and wonder if there is any existing math about it. Google searching did not turn anything up. Let $n\in \mathbb{N}$ be the dimension, and $x\in \...
1
vote
2answers
75 views

Are (quasi-)regular polytopes uniquely determined by their edge graph?

I consider polytopes $P\subset\Bbb R^n,n\ge 2$ of arbitrary dimension (intersection of finitely many halfspaces, therefore convex), which are vertex- and edge-transitive (also called quasi-regular). ...
1
vote
1answer
66 views

Reformulation of inequality constraint

Version 1 Let $\pi$ be a given permutation of the integers $\{1,\ldots,n\}$ and let $$\mathcal{X}=\{x\in\mathbb{R}_{+}^{n} \mid x_{\pi(1)}\geq\cdots\geq x_{\pi(n)}\}$$ Suppose we seek some $a \in \...
1
vote
1answer
55 views

Polytope in Minkowski sum

Is the following statement true? Suppose that $P$ is a polytope contained in the Minkowski sum $A+B:=\{a+b: a\in A, b\in B\}$ of two convex compact sets $A$ and $B$. Then there exist polytopes $Q\...
5
votes
1answer
158 views

$n$-sphere enclosing the Birkhoff polytope

I am not a mathematician by training, so please feel free to correct my logic or descriptions when necessary: Let $P$ denote a $\textit{permutation matrix}$: $$ \begin{equation} P := \{X \in \{0,1\}^{...
5
votes
1answer
54 views

What are the facets of the Birkhoff Polytope when $n=2$?

I've read in several sources that the number of facets of the Birkhoff polytope $\mathcal{B}(n)$ is $n^2$. Is this supposed to hold when $n=2$? Since $\mathcal{B}(2)$ has dimension $1$, the facets ...
0
votes
1answer
69 views

Lower bound for the number of edges in a Minkowski sum

I was wondering whether the following statement about a Minkowski sum of two polytopes is true: Let $P=P_1 + P_2$ be the Minkowski sum of two polytopes $P_1$ and $P_2$ in $\Bbb R^n$, i.e. $P=\{p_1+...
3
votes
2answers
63 views

Check if convex polytope contained inside a union of convex polytopes?

Suppose I have a polytope $\mathcal P$ and a set of other polytopes $\{\mathcal S_0,\dots,\mathcal S_N\}$. Is there a computationally efficient way to check that $\mathcal P\subseteq\bigcup_{i=0}^{N}\...
0
votes
0answers
64 views

(LP problem) Find an optimal plane that contains a set of points in its positive half-space, such that it does not coincide with another plane

Given is a set of points $S = \{s_1,...,s_N\in\mathbb{R}^n\}$ and a plane $H_1$ with $H_1^+ = \{ x \in \mathbb{R}^n ~\vert~ n_1^Tx - b_1 \geq 0\}$ being its positive half-space, such that $\forall s\...
0
votes
0answers
22 views

Finite overgroups of finite 4D point groups

In 3D, every finite point group is either prismatic, a subgroup of [4, 3] or a subgroup of [5,3]. This Wikipedia diagram, along with the rest of the article, seem to imply that in 4D, every finite ...
0
votes
0answers
15 views

What separates a cyclic polytope from a projective polytope?

I am having trouble understanding the difference between a cyclic polytope and a convex projective polytope as positive geometries. The link https://arxiv.org/pdf/1703.04541.pdf is the source of ...
0
votes
0answers
59 views

What's the collective term for the concepts of truncation, gyroelongation, snubification, etc., for polyhedra?

I recently watched a video on a youtube channel "DONG" led by Michael from Vsauce titled "Making every strictly convex deltahedron" Some concepts like elongation, gyroelongation, expansion, ...
0
votes
0answers
33 views

Combinatorial property of cross polytopes [duplicate]

I apologize in advance; I know that this site is for research-level mathematics, not for elementary learning ground. But I tried to understand the following question on my own but it is still ...