An Optimal Real-Time Algorithm for Planar Convex Hulls

An algorithm is described for the construction in real-time of the
convex hull of a set of n points in the plane.   Using an appropriate data
structure, the algorithm constructs the convex hull by successive
updates, each taking time O(log n), thereby achieving a total
processing time O(n log n).  

CACM July, 1979

Preparata, F.

Computational geometry, convex hull, planar set of
points, real-time algorithms, on-line algorithms.  

4.49 5.25 5.32

CA790702 DH August 22, 1979  2:07 PM

3151	4	3151
2997	5	3151
3151	5	3151
3151	5	3151
3151	5	3151