Is there an algorithm to find the edge vectors of a polytope?

443 Views Asked by At

Question:

Given some points $x^1,\dots,x^m \in \mathbb R^n$, is there an algorithm that finds the vectors along the edges of the polytope $$P = \mathrm{conv}(x^1,\dots,x^n)$$ formed by the convex hull of these points?

Definitions:

A polytope is the convex hull of finitely many points in $\mathbb R^n$. Let $P \subset \mathbb R^n$ be a polytope. A face of $P$ is a a subset $F \subset P$ of the form $$F = \arg \max\{c^Tx : x \in P\}$$ for some $c \in \mathbb R^n$. The dimension of a face of $P$ is the dimension of its affine hull. A vertex is a face of dimension zero and an edge is a face of dimension one. If $E$ is an edge of $P$ then $E = \mathrm{conv}(x, y)$ for some vertices $x$, $y$. An edge vector of a polytope $P$ is a vector $v \in \mathbb R^n$ such that $v=x-y$ for some vertices $x$ and $y$ for which $\mathrm{conv}(x,y)$ is an edge.

Example:

Let $x^1=(0,0), x^2=(1,0), x^3=(0,1), x^4=(1,1)$. The convex hull of these points is the square $$P=\mathrm{conv}(x^1, x^2, x^3, x^4)$$ whose edge vectors are given by $$\{(1,0), (0,1), (-1, 0), (0, -1)\}.$$ Note that $(1,1)=x^4-x^1$ is not an edge vector although it is the difference of two vertices.

1

There are 1 best solutions below

0
On BEST ANSWER

In a first step you have to determine which points are vertices of the convex hull. In a second step you can proceed as explained by kimchi in the comments.

A point $x_i$ is a vertex of $\mathrm{conv}\{x_1,...,x_n\}$ if

$$\max \{p^\top\! x_i\mid p^\top\! x_j \le 1 \text{ for all $j\not=i$}\}$$

is unbounded.

If $x_i,x_j$ are vertices, to determine whether $\mathrm{conv}\{x_i,x_j\}$ is an edge of the convex hull you can proceed as explained in this answer. You have to iterate this over all ${n\choose 2}$ vertex pairs. If it is an edge, you just compute $x_i-x_j$ to get its direction.

To compute the maxima in all these cases you will have to use linear programming algorithms which are standard and have many well-developed implementations (e.g. in Mathematica or MATLAB).