Back to the PSciCo homepage

Persistent Convex Hull Code

We have two fully persistent implementations of convex hull which are based on our simplicial complex interface.
  • IncrementalHull.sml is a basic incremental hull based on associating each unprocessed point with a visible face (i.e. a ray from the point to the face penetrates the face from the outside). The points are added one at a time, ripping out the portion of the hull that is is visible from the point and adding a tent from the point to the boundary of the removed region. We know of no bounds on the running time for this algorithm.

  • BulldozerHull.sml is a more sophisticated version of the incremental hull that has provable runtime bounds. The main differences are that the points are picked at random, and that the process of ripping out the visible region also keeps track of how the points associated with each removed face are moved onto one of the new tent faces. This is the "bulldozing" process. This randomized algorithm runs in 3d using O(n log n) floating point operations and O(n) operations on the simplicial complex (both expected case). Since the operations on the hull each take O(log n) time using the simplicial complex interface, the total running time is expected O(n log n).
  • The algorithms are designed to work in any dimension, although they have only been fully tested for 3d Convex Hulls. Both implementations conform to the HULL signature. The bulldozer algorithm is described in more detail in the paper
  • Persistent Triangulations. Guy Blelloch, Hal Burch, Karl Crary, Robert Harper, Gary Miller and Noel Walkington. To appear in the Journal of Functional Programming.
  • Other Information

  • change log
  • test code

  • Acknowledgements

    The PSCICO project is supported by NSF under the title "Advanced Languages for Scientific Computation Environments" as part of the Experimental Software Systems program within CISE. The grant number is 9706572.

    Back to the PSciCo homepage.