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?

Improve this question
$\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$
    – Zsbán Ambrus
    Commented 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$
    – Christopher
    Commented Apr 27, 2015 at 10:10

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
4
  • $\begingroup$ PPL gives wrong results in high dimensions: math.stackexchange.com/questions/2286233/… $\endgroup$
    – DSblizzard
    Commented 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$
    – Dima Pasechnik
    Commented 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
    Commented Aug 22, 2023 at 23:43
  • $\begingroup$ @Makogan - I've added a link in the answer to such a resource. $\endgroup$
    – Dima Pasechnik
    Commented Aug 23, 2023 at 11:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .