10
$\begingroup$

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?

$\endgroup$
2
  • $\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, 2015 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, 2015 at 10:10

1 Answer 1

10
$\begingroup$

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.

More info on double description and reverse search methods can be found in Komei Fukuda's Polyhedral FAQ

$\endgroup$
4
  • $\begingroup$ PPL gives wrong results in high dimensions: math.stackexchange.com/questions/2286233/… $\endgroup$
    – DSblizzard
    Aug 26, 2017 at 13:31
  • $\begingroup$ No, it's not giving wrong results there - please see the answer to your question I just posted. $\endgroup$ Aug 26, 2017 at 22:35
  • $\begingroup$ Do you know of a resource that explains either the double description method or the reverse search method from a pedagogical standpoint? $\endgroup$
    – Makogan
    Aug 22, 2023 at 23:43
  • $\begingroup$ @Makogan - I've added a link in the answer to such a resource. $\endgroup$ Aug 23, 2023 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.