# Testing whether two vertices are neighbours

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

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$.
• 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? – Brendan McKay Mar 30 '16 at 1:23