Convex Hulls of Finite Sets of Poin ts in Two and Three Dimensions

The convex hulls of sets of n poin ts in two
and three dimensions can be determined with O(n 
log n) operations.  The presented algorithms use the "divide
and conquer" technique and recursively apply 
a merge procedure for two nonin tersecting convex hulls.
 Since any convex hull algorithm requires at 
least O(n log n) operations, the time complexity of the
proposed algorithms is optimal within a multiplicative 
constant.

CACM February, 1977

Preparata, F. P.
Hong, S. J.

computational complexity, convex hull, optimal algorithms,
planar set of poin ts, spatial set of 
poin ts

4.49 5.25 5.32

CA770203 JB December 30, 1977  2:47 AM

2997	4	2997
2737	5	2997
2997	5	2997
2997	5	2997
2997	5	2997
3151	5	2997
2997	6	2997