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

Bhattacharya, Binay K. ; Sen, Sandeep (1997) On a simple, practical optimal output-sensitive randomized planar convex hull algorithm Journal of Algorithms, 25 (1). pp. 177-193. ISSN 0196-6774

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1006/jagm.1997.0869

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.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:53432
Deposited On:08 Aug 2011 12:09
Last Modified:08 Aug 2011 12:09

Repository Staff Only: item control page