Loading...
Please wait, while we are loading the content...
Similar Documents
Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Chan, Timothy M. |
| Abstract | We present simple output-sensitive algorithms that construct the convex hull of a set of n points in two or three dimensions in worst-case optimal O(n log h) time and O(n) space, where h denotes the number of vertices of the convex hull. 1 Introduction Given a set P of n points in the Euclidean plane E 2 or Euclidean space E 3 , we consider the problem of computing the convex hull of P , conv(P ), which is defined as the smallest convex set containing P . The convex hull problem has received considerable attention in computational geometry [11, 21, 23, 25]. In E 2 , an algorithm known as Graham's scan [15] achieves O(n log n) running time, and in E 3 , an algorithm by Preparata and Hong [24] has the same complexity. These algorithms are optimal in the worst case, but if h, the number of hull vertices, is small, then it is possible to obtain better time bounds. For example, in E 2 , a simple algorithm called Jarvis's march [19] can construct the convex hull in O(nh) time. ... |
| File Format | |
| Journal | Discrete & Computational Geometry |
| Journal | DISCRETE & COMPUTATIONAL GEOMETRY |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Worst-case Optimal Convex Hull Optimal Output-sensitive Convex Hull Algorithm Simple Algorithm Introduction Given Computational Geometry Considerable Attention Euclidean Plane Present Simple Output-sensitive Algorithm Running Time Convex Hull Problem Hull Vertex Time Bound Euclidean Space |
| Content Type | Text |
