Komei Fukuda, EPFL and ETHZ, Switzerland
Joint work with
Anders Jensen, ETHZ and Christophe Weibel, EPFL
There are quite a number of mathematical computations can be formulated
in one way or another as
problems on certain convex polyhedra in some vector space
. For
example, computation of the Voronoi diagram and the Delaunay triangulation
for a given set of points in
can be reduced to the
representation conversion (between V-representation and H-representation)
for convex polyhedra in
and
various software packages for the conversion are available, see [2].
On the other hand, there are many fundamental problems in polyhedral computation that are not yet sufficiently understood in terms of their (worst-case, average) complexities, the existence of efficient algorithms, relations to other problems, etc. These problems include (variants of ) the problems of computing the Minkowski addition of several convex polytopes, the volume of a convex polytope, projections of a convex polytope, and recognizing the convexity of the union of several convex polytopes. Note that the complexity of a problem depends very much on how input and output are specified (e.g. V-representation or H-representation) and thus there are many variants. Also, some problems can be efficiently solved if we restrict our attention to a special class of polytopes.
Although we are very far from having a ``complete'' set of polyhedral computation software tools, there are more and more software tools available. We are pleased to announce the availability of two new software packages with unique functionalities that reflect some recent progresses in polyhedral computation.
. It is an implementation in C++ language
of the reverse search algorithm [1] whose time complexity is
polynomially bounded by the sizes of input and output.
-variables. It is an implementation in C++ language
of the reverse search algorithm [4].
Both packages use GMP (GNU multi-precision library) and the exact LP solver of cddlib [3]. They are both licensed under GPL (GNU Public License).