Vinci

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 the state of the art algorithms for volume computation. It is the fruit of a research project carried out at the IFOR (Institute for Operations Research) at ETH Zürich, in collaboration with Benno Büeler and Komei Fukuda. The code is released under the GnuGeneral Public License.

download of version 1.0.5; this version is noticeably faster than the previously released one
documentation
an analysis of the different algorithms and their applicability to various classes of polytopes

Polytope files

The following is a collection of polytopes on which we tested our volume computation codes. The polytopes are given in the file format specified by David Avis and Komei Fukuda. We included the .ext- and .ine-files (if this sounds weird to you, you had better read the Vincidocumentation, it comprises a description of the file format). The data are split into separate files, each of them corresponding to a different problem class.

cube: hypercubes with -1 and 1 as vertex coordinates, in dimension 2 to 14.
cross: cross polytopes, the duals of the cubes above, also in dimension 2 to 14.
rh: polytopes constructed by randomly choosing hyperplanes tangent to the sphere; after unpacking, files rh_d_m will be created, where d stands for the dimension and m for the number of hyperplanes.
rv: dually to the previous category these polytopes have vertices randomly distributed on the sphere.
cc: cc_8_7 to cc_8_11, the product of two cyclic polyhedra with seven to eleven vertices, each in dimension four. The final dimension is therefore eight.
ccp: complete cut polytopes on five to seven vertices. The polytopes have been scaled by 2 and then translated by 1 to contain the origin in their interor. So their vertices have coordinates +1 and -1 now.
metric: after expansion, contains facets of the fourth (Fm_4) to sixth (Fm_6) metric polytope.

Vinci

Polytope files

Links