Computational Geometry

• Mixed Volumes
  • Package in Ansi-C, containing stand-alone programs and libraries.
  
  One may alternatively look into the FTP directory for the README file as well as individual libraries.

  These programs compute, in arbitrary dimension, the mixed and stable mixed volumes and for enumerating all mixed and stable mixed cells in a mixed subdivision. When the input points are polynomial supports then the mixed [resp. stable] volume bounds the number of their isolated complex toric (without zero coordinates) [resp. affine] roots. The software implements the lift-prune algorithm of Emiris-Canny (JSC article) based on the Huber-Sturmfels algorithm, and the stable volume modification of Emiris-Verschelde (article).

  • Maple functions for converting Maple objects to the input formats of the C programs (mapl2form), for calling the C program from within Maple (mixvol.mpl), as well as some additional Maple functions (maplib).

  ---

• Computing integer points in Minkowski sums Ansi-C implementation of the Mayan pyramid algorithm for computing a subset of the integer points in all n-fold Minkowski sums of a family of n+1 convex (Newton) polytopes in n dimensions. Publication(.ps.gz). Improved algorithm and implementation by Kyriakos Zervoudakis here.

---

• Convex Hulls in General Dimension Contains an Ansi-C implementation of the Beneath-Beyond algorithm for constructing convex hulls and computing their volume in arbitrary dimension. Degenerate inputs are handled by the perturbation scheme of Emiris and Canny. Instructions (README file) for copying and installing. Algorithmica article

---

• Exact Convex Hulls Modification of the general-dimension code in order to merge coplanar facets and delete the degenerate ones, in up to 3 dimensions. Vertices are enumerated in CCW order from the outside. Vizualisation is possible with Geomview. Instructions for copying/installing, IJCGA article (.ps)

---

• More software for polynomials.

  ---