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 log h) time output-sensitive algorithm for the planar convex hull problem. The basic algorithm is similar to the algorithm presented by Chan, Snoeyink, and Yap (in ''Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, 1995,'' pp. 282-291), where the median-finding step is replaced by an approximate median. We analyze two such schemes and show that for both methods, the algorithm runs in expected O(n log h) time. We further show that the probability of deviation from expected running time approaches 0 rapidly with increasing values of n and h for any input. Our experiments suggest that this algorithm is a practical 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 appear), but our analysis is substantially different. (C) 1997 Academic Press.