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