On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm
✍ Scribed by Binay K Bhattacharya; Sandeep Sen
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 212 KB
- Volume
- 25
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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.