Computational Geometry

Mixed Volumes

Package
in AnsiC, containing standalone 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 liftprune algorithm of EmirisCanny
(JSC article)
based on the HuberSturmfels algorithm,
and the stable volume modification of EmirisVerschelde
(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
AnsiC implementation of the Mayan pyramid algorithm for computing
a subset of the integer points in all nfold Minkowski sums
of a family of n+1 convex (Newton) polytopes in n
dimensions.
Publication(.ps.gz).

Convex Hulls in General Dimension
Contains an AnsiC implementation of the BeneathBeyond
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 (.ps)

Exact Convex Hulls
Modification of the generaldimension 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 (.dvi) and
(.ps)

Mixed Subdivisions
AnsiC implementation of the lifting algorithm for computing
the entire mixed subdivision of the Minkowski sum of n convex
polytopes in n dimensions. Includes option to produce output
appropriate for visualization with Geomview.
An
example of three 2dimensional polygons.
J.ACM article
(.dvi)
and
(.ps).

More
software for polynomials.
Ioannis Z Emiris
18 june 2001.