# Computionally efficient vertex enumeration for (convex) polytopes

Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be performed in $\mathcal{O}(|V|^{\lfloor d/2 \rfloor})$, cf. [1]. Practically, one would use the double description method, cf. [2], and cf. cddlib for an implementation of the former.

In my application, I have to solve a rather large number of such vertex enumeration problems in let's say dimension $10$. Unfortunately, ccdlib is too slow and causes numerical problems (the GMP version is even slower).

Moreover, for my application it suffices to find a superset of $V$. Hence, I thought there might be a way to decompose $P$ into "simpler" polytopes such that the vertex enumeration for each such polytope could be performed much faster.

Is anybody aware of such method?

• How is the polytope defined? Is it given as an intersection of half-planes? If so, can this problem be transformed to the dual problem of enumerating all the facets of the convex hull if the vertices are given? Apr 27 '15 at 9:17
• Yes, it is an $\mathcal{H}$-polytope, i.e., intersection of finitely many affine half-spaces. Yes, the facet and the vertex enumeration problem are strongly polynomial equivalent. Apr 27 '15 at 10:10

cddlib is rather old; a much more efficient implementation of the double description method is in PPL (Parma Polyhedra Library). One frontend to PPL can be found in Sagemath: http://www.sagemath.org/doc/reference/geometry/sage/geometry/polyhedron/constructor.html PPL will perform computations exactly.

Apart from the double description there is the reverse search, a method consisting of "walking" over the vertices, implemented in lrs: http://cgm.cs.mcgill.ca/~avis/C/lrs.html and it might work better for your problems.

• PPL gives wrong results in high dimensions: math.stackexchange.com/questions/2286233/… Aug 26 '17 at 13:31
• No, it's not giving wrong results there - please see the answer to your question I just posted. Aug 26 '17 at 22:35