Access Restriction

Author Hong, S. J. ♦ Preparata, F. P.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Spatial set of points ♦ Convex hull ♦ Planar set of points ♦ Computational complexity ♦ Optimal algorithms
Abstract The convex hulls of sets of n points 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 nonintersecting 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.
Description Affiliation: Univ. of Illinois, Urbana (Preparata, F. P.) || IBM Systems Product Division, Poughkeepsie, NY (Hong, S. J.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 2
Page Count 7
Starting Page 87
Ending Page 93

Open content in new tab

   Open content in new tab
Source: ACM Digital Library