Let $P$ be a polytope given by a vertex description, i.e., $P=conv(\{x_1,\ldots,x_m\})\subset\mathbb{R}^n$.

Is there an efficient (i.e., not relying on Linear Programming) algorithm to compute the edge skeleton of $P$ ?

More generally, given a polytope $P=conv(\{x_1,\ldots,x_m\})$ AND its edge skeleton $ES=\{(i,j): (x_i,x_j) \text{ is an edge of } P\}$, is there an efficient algorithm to update the skeleton after insertion of a new vertex $x_{m+1}$, i.e., to identify the subset of vertices $I\subseteq\{1,\ldots,m\}$ such that $x_i,x_{m+1}$ is an edge of $conv(P,x_{m+1})$ ?

This problem can easily be solved by LP: Given two vertices $x_i,x_j$ , one can test if the mid-point $(x_i+x_j)/2$ can be expressed as a convex combination involving the point $x_k$ (with a positive weight), for each $k\notin\{i,j\}$. However, this naive approach seems to be highly nonefficient, as it involves solving $(m-2)$ LPs to test for the membership $(i,j)\in ES$...

I found a recent related paper https://arxiv.org/abs/1412.3987 that does the job when $P$ is given by an optimization oracle and a superset of vertex directions, but this seems to be a more complicated setup than a vertex description, and it also relies on linear programming.

  • Having a look at the cited article, we can actually reduce the problem of finding adjacent points to $x_1$ to the problem of find extreme points of a V-polytope, using a single LP. Here is how it works: 1) Solve an LP to find an hyperplane separating $x_1$ from the other vertices, i.e. a vertex $h$ such that $x_1^T h<0$, and $x_i^T h\geq 0$, $\forall i >1$. 2) For each $i>1$, denote by $y_i$ the intersection of the segment $[x_1,x_i]$ with the hyperplane $H=\{x:h^Tx=0\}$. 3) The neighbour vertices of $x_1$ are in one-to-one correspondence with the extreme points of $Y=conv\{y_2,...,y_m\}$. – guigux Dec 4 at 12:57
  • So, what is the status of the problem of enumerating extreme points of a convex hull of n points in d dimensions? According to this article:pdfs.semanticscholar.org/bd95/…, this can be done in O(nm), where m<n is the number of extreme points, but I don't really understand the claim, because the algorithm solves a bunch of linear programs with d variables and O(m) constraints... – guigux Dec 4 at 13:05
  • See Vertex enumeration problem for a bit more detail on the complexity of the Avis-Fukuda enumeration algorithm. – Joseph O'Rourke Dec 4 at 17:21
  • The Avis Fukada algorithm is for polytopes described by linear inequalities. Here, we ask for the extreme points of a convex hull of points... – guigux Dec 4 at 21:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.