Chan's divide, prune, & conquer algorithm is like Quickhull, but an
extra pruning step makes it
optimal and output sensitive---running in O(n log h) in the worst case.
See T. M. Chan and J. Snoeyink and C. K. Yap, "Primal dividing and
dual pruning: Output-sensitive construction of 4-d polytopes and
3-d {Voronoi} diagrams,"
Discrete Comput. Geom., 18, 1997, p. 433--454.
(Back to LineTesting.)
Known bugs: So far we have implemented only the version with expected O(n log h) performance on the worst point set.
Code by Jack Snoeyink, University of British Columbia Back to Jack's Computational Geometry Demo page.