1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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\}$. $\endgroup$
    – guigux
    Commented Dec 4, 2018 at 12:57
  • $\begingroup$ 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... $\endgroup$
    – guigux
    Commented Dec 4, 2018 at 13:05
  • $\begingroup$ See Vertex enumeration problem for a bit more detail on the complexity of the Avis-Fukuda enumeration algorithm. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 4, 2018 at 17:21
  • $\begingroup$ The Avis Fukada algorithm is for polytopes described by linear inequalities. Here, we ask for the extreme points of a convex hull of points... $\endgroup$
    – guigux
    Commented Dec 4, 2018 at 21:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .