1
$\begingroup$

I face the following problem: I am given a high-dimensional, convex, bounded polyhedron in both vertex description: $X = \mathrm{conv} \, \{ v_1, \ldots, v_K \}$ and halfspace description: $X = \{ x \in \mathbb{R}^k \, : \, A x \leq b \}$. I can assume that the halfspace description does not contain any redundant inequalities, but in general some of the vertices will be highly degenerate.

I would like to know whether two specified vertices $v_i$ and $v_j$ are neighbours, that is, they are connected by an edge. This problem is fairly simple in dimensions 2 and 3, but I'm interested in the high(er)-dimensional case.

Could anybody please point me into the right direction?

Many thanks

$\endgroup$
1
$\begingroup$

You should first check that $v_i$ and $v_j$ are both vertices of $X$. Given the description $X = \{ x \in \mathbb{R}^k \, : \, A x \leq b \}$, this is easy.

Suppose that $A$ is an $m \times n$ matrix. Then $v \in X$ is a vertex if and only if $A'v=b'$ for some subsystem $A'x \leq b'$ of $Ax \leq b$, where $A'$ has rank $n$. Such a subsystem is called a basis for $v$.

Now, two vertices $v_i$ and $v_j$ of $X$ are adjacent if and only if there is a rank-$(n-1)$ subsystem $A^*x \leq b^*$ of $Ax \leq b$ such that $A^*L=b^*$, where $L$ is the line through $v_i$ and $v_j$.
Thanks to Brendan McKay for this last step.

$\endgroup$
  • $\begingroup$ Since there can be many bases for a vertex, it isn't clear how to carry out the last step efficiently. Wouldn't it be better to look for a rank-$(n{-}1)$ subset $A^*x\le b^*$ of the constraints such that $A^*L=b^*$ where $L$ is the line through the two vertices? $\endgroup$ – Brendan McKay Mar 30 '16 at 1:23
  • $\begingroup$ Yes, your suggestion is a much better way to do the last step. I edited it in. Thanks! $\endgroup$ – Tony Huynh Mar 30 '16 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.