Convex hulls of finite sets of points in two and three dimensions
- 1 February 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 20 (2) , 87-93
- https://doi.org/10.1145/359423.359430
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.Keywords
This publication has 7 references indexed in Scilit:
- An efficient algorith for determining the convex hull of a finite planar setPublished by Elsevier ,2002
- On Finding the Maxima of a Set of VectorsJournal of the ACM, 1975
- Determining the minimum-area encasing rectangle for an arbitrary closed curveCommunications of the ACM, 1975
- On the identification of the convex hull of a finite set of points in the planeInformation Processing Letters, 1973
- Measuring Concavity on a Rectangular MosaicIEEE Transactions on Computers, 1972
- An Algorithm for Convex PolytopesJournal of the ACM, 1970
- Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1968