ChanDC convex hull in the plane

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.