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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Mar 30, 2016 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
    Commented Mar 30, 2016 at 6:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .