Subject 6.02: Where do I get source for convex hull?
For n-d convex hulls, try Clarkson’s hull program (exact arithmetic) or Barber and Huhdanpaa’s Qhull program (floating point arithmetic). Qhull handles numeric precision problems by merging facets. The output of both programs may be visualized with Geomview. In higher dimensions, the number of facets may be much smaller than the number of lower-dimensional features. When this is the case, Fukuda’s cdd program is much faster than Qhull or hull. There are many other codes for convex hulls. See Amenta’s list of computational geometry software. References: Amenta: http://www.geom.umn.edu/software/cglist/ Barber & http://www.geom.umn.edu/locate/qhull Huhdanpaa ftp://geom.umn.edu/pub/software/qhull.tar.Z Clarkson: http://cm.bell-labs.com/netlib/voronoi/hull.html / ftp://cm.bell-labs.com/netlib/voronoi/hull.shar.Z Geomview: http://www.geom.umn.edu/locate/geomview / ftp://geom.umn.edu/pub/software/geomview/ Fukuda: http://www.ifor.math.ethz.ch/staff/fukuda/cdd_home/cdd.html / ftp://ftp.ifor.ma
