The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

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.


  • Download Files (local site)
  • Ken Clarkson's Webpage
  • Official site

    Problem Links

      
    Convex Hull (6)
      
    Triangulation (5)



    This page last modified on 2008-07-10 .
    www.algorist.com