Clarkson's higher dimensional convex hull code
Clarkson's higher dimensional convex hull code
Hull is an ANSI C program by Ken Clarkson of Bell Laboratories
that computes the convex hull of a point set in general (but small!)
dimension.
The input is a list of points, and the output is a list of facets of the convex hull of the
points, each facet presented as a list of its vertices.
(The facets are assumed to be simplices, such
as triangles in 3d; this is enforced by tiebreaking, giving a triangulation
of a facet by "placing".)
The program can also compute Delaunay triangulations and alpha shapes, and
volumes of Voronoi
regions.
The program uses exact arithmetic when possible, with a moderate speed penalty.
(Typically a factor of 2 or 3 for Delaunay triangulation,
less for convex hulls). Output in postscript
and OFF format for geomview is supported.
Ken Clarkson's home page
Download Files (local site)
Problem Links
Convex Hull (6)
About the Book
Send us Mail
Go to Main Page
This page last modified on Jun 2, 1997.