Introducing New Software Tools in Polyhedral Computation

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 $ {\Bbb R}^d$ . For example, computation of the Voronoi diagram and the Delaunay triangulation for a given set of points in $ {\Bbb R}^d$ can be reduced to the representation conversion (between V-representation and H-representation) for convex polyhedra in $ {\Bbb R}^{d+1}$ 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.

  1. Minksum [6] is a program to compute the V-representation (i.e. the set of vertices) of the Minkowski addition of several convex polytopes given by their V-representation in $ {\Bbb R}^d$ . 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.

  2. Gfan [5] is a program to list all reduced Gröbner bases of a general polynomial ideal given by a set of generating polynomials in $ n$ -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).


K. Fukuda.
From the zonotope construction to the Minkowski addition of convex polytopes.
Journal of Symbolic Computation, 38(4):1261-1272, 2004.

K. Fukuda.
Polyhedral computation FAQ, 2004.
Both html and ps versions available from

K. Fukuda.
cdd, cddplus and cddlib homepage.
Technical report, Swiss Federal Institute of Technology, Lausanne and Zurich, 2005.

K. Fukuda, A. Jensen, and R. Thomas.
Computing Gröbner fans.
Technical report.
In preparation.

A.N. Jensen.
Gfan version 0.1: A User's Manual.
Department of Mathematical Sciences, University of Aarhus and Institute for Operations Research, ETH Zurich, 2005.
available from

C. Weibel.
Minksum version 1.1.
Mathematics Institute, EPF Lausanne, 2005.
available from

Komei Fukuda 2005-05-02