Computational Geometry

• Mixed Volumes
  • Package in Ansi-C, containing stand-alone programs and 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 (JSC article); see also our stable volume computation (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: 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 (paper). Improved algorithm here.

  ---

• Exact Convex Hulls. : Ansi-C implementation of the Beneath-Beyond algorithm for constructing convex hulls and computing their volume in arbitrary dimension. Degenerate inputs are handled by our perturbation scheme (article).
  In up to 3D: Modification of the general-dimension code in order to merge coplanar facets and delete the degenerate ones (article).

  ---

• More software for polynomials.

  ---