ON A SIMPLE, PRACTICAL, OPTIMAL, OUTPUT-SENSITIVE RANDOMIZED PLANAR CONVEX-HULL ALGORITHM

In this paper we present a truly practical and provably optimal O(n lo g h) time output-sensitive algorithm for the planar convex hull proble m. The basic algorithm is similar to the algorithm presented by Chan, Snoeyink, and Yap (in ''Proceedings of the 6th ACM-SIAM Symposium on D iscrete Algorithms, 1995,'' pp. 282-291), where the median-finding ste p is replaced by an approximate median. We analyze two such schemes an d show that for both methods, the algorithm runs in expected O(n log h ) time. We further show that the probability of deviation from expecte d running time approaches 0 rapidly with increasing values of n and h for any input. Our experiments suggest that this algorithm is a practi cal alternative to the worst-case O(n log n) algorithms such as Graham 's and is especially faster for small output-sizes. Our approach bears some resemblance to a recent algorithm of Wenger (Algorithmica, to ap pear), but our analysis is substantially different. (C) 1997 Academic Press.