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.
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).