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?

  • $\begingroup$ 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? $\endgroup$ Apr 27 '15 at 9:17
  • 1
    $\begingroup$ 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. $\endgroup$ 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.


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.