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.

- Detail toggles the vertex numbers and some of the edge weights.
- Animate toggles some animation of partial computation
- Update is the button you push when the input is ready; If comparing times, click twice because the first time may include loading or swapping time.
- Random generates 50 random points
- Clear All and Delete Last give minimalist editing.

Code by Jack Snoeyink, University of British Columbia Back to Jack's Computational Geometry Demo page.