Introduction

The volume is one of the central properties of a convex body, and volume computation is involved in many hard problems. Applications range from rather classical ones as in convex optimisation to problems in remote fields like algebraic geometry where the number of common roots of polynomials can be related to a special polytope volume.

Part of the fascination of the subject stems from the discrepancy between the intuitive notion of "volume" and the actual hardness of computing it. Despite this discouraging complexity - algorithms in general need exponential time in the input dimension - steadily growing computer power enables us to attack problems of practical interest.

Vinci is an easy to install C package that implements several algorithms for volume computation. It is the fruit of a research project carried out at the end of the 1990s at the IFOR (Institute for Operations Research) of the ETH Zürich, in collaboration with Benno Büeler and Komei Fukuda. The code is released under the GNU General Public License (GPL).

It accompanied the original publication

• Benno Büeler, Andreas Enge and Komei Fukuda:
  Exact Volume Computation for Polytopes: A Practical Study.
  In Gil Kalai and Günter M. Ziegler (editors):
  Polytopes — Combinatorics and Computation
  DMV Seminar vol. 29.
  Birkhäuser Verlag, Basel 2000, pp. 131–154.

which analyses the different algorithms and their applicability to various classes of polytopes.