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
0 answers
13 views

What is an upper bound on the diameter of a convex polytope?

Given a convex polytope defined by $Ax \le b$, with $V = \{ x_1, \ldots, x_n \}$ vertices, I would like to find the maximal distance $\max_{i,j} || x_i - y_i||_2$ as a function of $A$ and $b$ (some ...
user avatar
  • 133
0 votes
0 answers
34 views

Find in which face lie a point on a hyper polytope, inscribed in an hyper unit-sphere (and how to generate this hyper polytope)

I am working on clustering normalized point in a k dimension space. At first i used Spherical LSH strategy where i used random planes to cut the hyper-sphere but it induces a lot of random (because i ...
user avatar
2 votes
0 answers
25 views

120 cell generated from quaternions

The two quaternions $\omega={1\over 2}(-1,1,1,1)$ and $q={1\over 4}(0,2,\sqrt{5}+1,\sqrt{5}-1)$ generate a finite group under multiplication with 120 elements that form the vertices of a 600 cell, ...
user avatar
  • 156
0 votes
2 answers
33 views

Finding containment between convex polytopes

Given 2 polytopes, either by their H-representations: $p_1: Ax\le b, p_2: Cx\le d$, where $b,d$ are real-valued vectors, $A,C$ are real-valued matrices, or by their V-representations: $p_1 = conv(p_{...
user avatar
0 votes
1 answer
44 views

Polyhedra intersection

If $A$ and $B$ are polyhedra, how do we show that the intersection $A ∩ B$ is a polyhedron. Does the same apply if they are both polytopes, will the intersection $A ∩ B$ also be a polytope? The ...
user avatar
  • 47
0 votes
0 answers
19 views

Tiling curved 3D space

A flat plane can be tiled, for example, with regular hexagons. If you try to tile a sphere with hexagons, however, it doesn't work--you have to introduce 12 pentagons to complete the tiling. Try to ...
user avatar
5 votes
2 answers
142 views

Minimal polytope enclosing a sphere

Given a unit ball in d dimensions (euclidean distance) and an allotment of points $n > d$, can we choose the set of n points such that their convex hull contains the ball and the volume of the ...
user avatar
  • 51
0 votes
1 answer
26 views

On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope

Crossposted at Operations Research SE Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid ...
user avatar
1 vote
1 answer
145 views

Point in Polytope?

Context: This question is somewhat identical to this on MathOverflow, it’s different in that it only focuses on the formula of the solution to the underlying problem. Suppose I have a convex hull $H$ ...
user avatar
  • 177
0 votes
2 answers
48 views

How to calculate the centroid of a Polytope?

Given a polytope is divided into simplexes, is it correct to calculate the centroid of the polytope as the average sum of its simplex centroid coordinates
user avatar
  • 177
1 vote
0 answers
48 views

What's the combination of vectors with all coeffiencts between 0 to 1?

Assume a combination of the form: $\vec{S}=\sum_ip_i\vec{v}_i$ with $0\le p_i\le 1$, what is this combination called? And considering the set: $$\mathcal{S}=\{\sum_ip_i\vec{v}_i \mid 0\le p_i\le 1\}$$ ...
user avatar
0 votes
1 answer
80 views

Ray through Polytope boundary(vertex/surface)?

This is a follow up problem to the question I asked sometime earlier also a similar problem to this, please what's the best way to quickly determine if a ray originating from a point intersects a n-...
user avatar
  • 177
1 vote
0 answers
44 views

Fastest way to solve vertex enumeration problem in python

I have a set of 73 linear non-strict inequalities that describe a convex polytope in the 36-dimensional space. All but one of the inequalities are of the form $x>=b$ or $x<=b$. In every but one ...
user avatar
  • 11
0 votes
1 answer
49 views

Rewriting an equation as a set of inequalities

I have a set $\\{x_1,x_2 \dots , x_d \in \mathbb{R} : |x_1| + |x_2| + \dots + |x_d| \leq 1 \\}$ and i would like to rewrite it as $\\{ u \in \mathbb{R}^d : Au \leq \textbf{1} \\}$ , where $\textbf{1}$ ...
user avatar
0 votes
0 answers
20 views

Two definitions about reflexive polytopes

I am working through Computing the Continuous Discretely and they give the definition of a reflexive polytope as $$ P=\{x \in \mathbb{R}^d : Ax \leq 1\}$$ where all entries from $A$ are integers. It's ...
user avatar
1 vote
0 answers
37 views

Uniformly sampling from the cone of feasible directions in case of linear inequalities.

I'm working on an algorithm that is minimizing some loss function restricted to a polytope in $\mathbb{R}^n$: $$ \mathcal{X}= \{ x \in \mathbb{R}^n : \sum_{i=1}^n x_i \leq 1, x_i \geq 0, \ i=1,\dots,n\...
user avatar
  • 11
0 votes
1 answer
49 views

Given a simplex $S$ with vertex set V, show that any the convex hull of any subset $V' \subseteq V$ is also a face of $S$.

Not looking for an outright solution but some back-and-forth. My thoughts so far: A face of any polytope $S$ can be defined as $F = H \cap S,$ where $H$ is some supporting hyperplane of $S$. We know ...
user avatar
  • 127
0 votes
0 answers
8 views

Uniform distribution over order simplex

Consider the set of all vectors $x \in [0,1]^K$ that are monotone, i.e. $0\leq x_1\leq x_2\leq ... \leq x_K\leq 1$. This set is known as orthoscheme or order simplex. Is there a formula for the ...
user avatar
0 votes
0 answers
14 views

Proving the hypercube is dual to the crosspolytope

As a lemma to a homework question, I'm trying to prove that the crosspolytope is dual to the hypercube. I can't tell if it follows trivially from the definition or not. We define the hypercube as $C_d ...
user avatar
  • 127
0 votes
1 answer
19 views

Edges of the 4_21 polytope

How to get the edges of the $4_{21}$ polytope? Given the vertices, and given that it is convex, I can theoretically get them with the R package cxhull. But there are 240 vertices of dimension 8, and ...
user avatar
0 votes
0 answers
15 views

Proving a relationship between vertices, faces, and the face lattice.

Let $P$ be a polytope with vertex set $V$ such that $v_1, v_2, ..., v_k \in V.$ Let $F \in \Phi(P)$ be a face of $P$, where $\Phi(P)$ is the face lattice of $P$. I'd like to show that if $\frac{1}{k}(...
user avatar
  • 127
1 vote
0 answers
18 views

Counting the faces of a polytope and its dual

I have developed the way to count the faces of a $d-$dimensional polytope $P$ and show that the face numbers satisfy the Euler-Poincare relation, and we'll say $C(k,P)$ is the number of $k-$...
user avatar
  • 127
1 vote
0 answers
18 views

Counting number of n-faces in a uniform 7-polytope

Building off of What are the formulas for the number of vertices, edges, faces, cells, 4-faces, ..., $n$-faces, of convex regular polytopes in $n \geq 5$ dimensions? , Are there formulas for the ...
user avatar
0 votes
4 answers
84 views

Ray polytope intersection?

Context: I am working with polytopes, I am looking for a general way of testing if a point exists within an n-polytope by a vector ray-cast (most of what I have been able to gather while hunting via ...
user avatar
  • 177
0 votes
0 answers
19 views

Some questions regarding k-permutahedra

We define the k-permutahedron $P$ as the convex hull of all permutations of $(1,2,...,k)$. First, I'd like to compute the affine hull of $P$. My observations for $n = 2$ and $n = 3$ are that the ...
user avatar
  • 127
0 votes
2 answers
41 views

Prove that the number of $k$-simplexes in an $n$-orthoplex is $2^{k+1}\binom{n}{k+1}$ (where $n,k \in \mathbb{N}$ with $0 \leqslant k < n$)?

In the book 'Regular Polytopes' (H.S.M. Coxeter, 1973), Coxeter describes the $n$-orthoplex (which I will refer to from now on as $\beta_{n}$, and is the $n$-dimensional analogue of the octahedron) ...
user avatar
1 vote
0 answers
39 views

Proving that the free sum of two Polyhedra is a Polyhedra

For definitions and reference, we are working from Guenter Ziegler's Lectures on Polytopes. We define the free sum as follows. Given two polyhedra $P, Q \in \mathbb{R}^d$, the free sum $P \bigoplus Q =...
user avatar
  • 127
2 votes
0 answers
27 views

Orthogonal projections of $d$-dimensional skeleta of $n$-cubes in $\mathbb{R}^n$.

The question Let $I$ be the unit $n$-cube in $\mathbb{R}^n$, defined by the inequalities $\{0\leq x_i\leq 1 \, |\, i=1,2,...,n\}$. Define $\partial_d I$ to be its $d$-dimensional skeleton, or, in ...
user avatar
0 votes
1 answer
30 views

Is there a polyhedron whose face lattice is a given lattice with the "diamond property"?

I learned that every $(k-2)$-face is contained in exactly two facets in a $k$-dimension polyhedra from 'Theory of linear and integer programming'. So every face lattice of polyhedra satisfies the &...
user avatar
2 votes
1 answer
61 views

Why does Klein's quartic curve have 24 heptagonal faces/56 triangular faces as a tiling?

I first learned about Klein's quartic from John Baez' blog: https://math.ucr.edu/home/baez/klein.html In it, he claims that if we want to wrap up the heptagonal tiling of the hyperbolic plane by "...
user avatar
0 votes
0 answers
29 views

Faces for Polytopes.

We are using the definition for faces, as an intersection with a supporting hyperplane. I have to show, $F$ is a face of polyhedron $Q$, if and only if $F$ is convex and for every $0 < x < 1$, $...
user avatar
2 votes
0 answers
40 views

Generalized barycentric coordinates using only the H-representation (i.e., only facets, not vertices)

I have a polytope in $\mathbf{R}^n$ given by the inequality $\boldsymbol{A}\boldsymbol{x}\le \boldsymbol{b}$, where $\boldsymbol{x}\in\mathbf{R}^n$, and $\boldsymbol{A}$ is a rectangular matrix. I was ...
user avatar
  • 85
2 votes
1 answer
33 views

Characteristic vector of independent points in a graph

I'm trying to understand vertex packing polytopes, and have run into some definitions that I don't understand properly. In the summary of this paper, the authors say that the vertex packing polytope ...
user avatar
  • 323
0 votes
0 answers
14 views

Redundant constraints and linear dependency

Consider the following polyhedron $S=\{Ax\leq b \mid x\geq 0\}$, where $A\in \mathbb{R}^{n\times m}$ and $b\in\mathbb{R}^n$. Is the following statement true: If an inequality $A_k x\leq b_k$ for $k\in ...
user avatar
1 vote
0 answers
34 views

Boundary of a zonotope

I am currently learning about zonotopes but I am having troubles understanding the concept of it. I know that a zonotope is defined as $$\left\lbrace x : x=c +\sum_{i=1}^k \xi_ig_i, \xi_i \in \lbrack -...
user avatar
  • 578
2 votes
2 answers
35 views

Characterization of interior points of a convex polytope

I'm currently working through Convex Polytopes by Arne Brøndsted. Exercise 3.1 asks the following Let $P=\text{conv}\ \{x_1,\ldots,x_n\}$ be a polytope in $\mathbb R^d$. Show that a point $x$ is in $\...
user avatar
  • 3,989
-1 votes
1 answer
59 views

Inferring dimension of a polyhedron from a point

If we have a polyhedron $P = \{x\in\mathbb{R}^n \mid Ax \leq b \}$, and we find a point $x\in P$ such that $x$ satisfies at least $n$ of the $Ax\leq b$ (linearly independent) inequalities strictly, ...
user avatar
3 votes
0 answers
97 views

Upper-bound on volume of polytope inscribed in the sphere

To my great surprise, I was unable to find any general reference on the volume of (symmetric) polytopes inscribed in, say, the unit sphere. Let $P = absconv(v_1,\dots,v_k) $ where the $v_i$'s are unit ...
user avatar
  • 251
1 vote
1 answer
58 views

When is a polyhedron uniquely determined by its projections?

Let $P$ denote a polyhedron in $\mathbb{R}^D$ defined by the intersection of $k$ halfspaces, so $P = \{x\in\mathbb{R}^D : Ax\le b\}$ for $A\in\mathbb{R}^{k\times D}$, $b\in\mathbb{R}^k$. For a subset ...
user avatar
  • 2,945
5 votes
1 answer
180 views

Caratheodory's theorem with two vectors

Let $S\subset \mathbb R^n$ be given. Take $x\in conv(S)$. Then by Caratheodory's theorem, we can find $n+1$ vectors in $S$ such that $x$ is in the convex hull of these vectors, i.e., there is $S'\...
user avatar
  • 42k
3 votes
1 answer
90 views

Generalization of Caratheodory's theorem

Conjecture: Let $S\subseteq \mathbb{R}^d$ and let $x, y \in \text{conv}(S)$, the convex hull of $S$. Then, $x, y \in \text{conv}(S')$ for some $S' \subseteq S$ such that $|S'| \leq d+2$. Basically, ...
user avatar
0 votes
1 answer
51 views

What does mean $\mathrm{conv}\{\{+1, -1\}^d\}$

What does mean $\mathrm{conv}\{e_1 , -e_l , \ldots , e_d , -e_d\}$ and $\mathrm{conv}\{\{+1, -1\}^d\}.$ I could not understand, need a simple explanation.
user avatar
  • 1
2 votes
1 answer
61 views

Are any higher-dimensional analogues of triangles flexible?

I don't know if my terminology is correct, so bear with. Triangles are 'inflexible'. By that, I mean that if you consider a triangle to be a graph of 3 edges and 3 vertices in a closed loop then you ...
user avatar
  • 123
0 votes
0 answers
32 views

The space of all convex combinations including given set.

It is possibly a simple question with me grossly overcomplicating things, but I'm not exactly familiar with the topic. The question is long and consists of three parts. A prerequisite construction I ...
user avatar
  • 2,978
-1 votes
1 answer
28 views

How to expand the following notation?

Can someone help me to expand the below equation for N=2 and N=3? $f_i=\sum \{e_i:j\leq i \leq k\}$ for some $1\leq j\leq k\leq N$. Here $e_i$ is the unit vector of coordinate i in an N-dimensional ...
user avatar
  • 1
2 votes
2 answers
67 views

Given two isomorphic convex uniform polytopes in $R^n$, is there a way to embed them in a higher dimension so the vertices are all unit distance apart

$P$ and $Q$ are two isomorphic convex uniform polytopes in $\mathbb{R}^n$. Is there a space $\mathbb{R}^m$, where $n \lt m$, in which we can embed $P$ and $Q$, such that for each vertex $p\in P$ and $...
user avatar
  • 133
2 votes
1 answer
33 views

How to visualise this weighted combination?

Let $x_1, ..., x_n$ be a set of real numbers. The convex polytope formed from $x_1, ..., x_n$ is given by the set of all $$\sum_i \alpha_i x_i,$$ where $\alpha_i \geq 0$ satisfy $\sum_i \alpha_i =1$. ...
user avatar
  • 65
1 vote
0 answers
46 views

When is a convex polyhedron bounded?

Consider the following sets $$ \mathcal{X}_y\equiv \{x\in \mathbb{R}^d: \quad f(y)*x\leq 0_k\}\quad \text{for each }y\in \mathbb{R}^j\\ \mathcal{Y}\equiv\{y\in \mathbb{R}^j: \quad \exists \quad x\in \...
user avatar
  • 242
0 votes
0 answers
15 views

Conditions for $Ax+b\leq\vec0$ and $Cx+d=\vec0$ to describe a bounded polytope

I am looking for a criterion on the matrixes $A, C$ and the vectors $b, d$ that tell me whether $Ax+b\leq\vec0$ and $Cx+d=\vec0$ describes a bounded polytope. I would strongly prefer an criterion in ...
user avatar
2 votes
1 answer
84 views

Zonotope: Image of the Diagonals of a Hypercube Under a Linear Map

Let $A \in \mathbb{R}^{m \times n}$ be a matrix where $m \leq n$, and let $H = [-1,1]^n$ be the unit hypercube. One can form the zonotope $\mathcal{Z}(A) = \{Ax : x \in H\} \subset \mathbb{R}^m$, ...
user avatar

1
2 3 4 5
14