On a simple, practical optimal output-sensitive randomized planar convex hull algorithm

Abstract

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[2], 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 ofnandhfor 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[13], but our analysis is substantially different.