| A New Ultimate Convex Hull Algorithm in R² (2000) | |||||||||||||
Abstract | |||||||||||||
| We present a very simple algorithm - NEWHULL - to find the convex hull of S = {P 1 , . . . , Pn}, n given points in R 2 . It may be thought of as a variant of Quickhull; however if the hull of S has h vertices, the algorithm runs in time #(n log h), worstcase. On the average it is much faster. Analysis suggests that NEWHULL should be twice as fast as the "ultimate" algorithm of Kirkpatrick and Seidel, and experimental evidence bears this out. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||