# Compute the edge-skeleton of a polytope given by its vertices

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 '18 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 '18 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 '18 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 '18 at 21:28