|
 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
 |
2
|
|
| |
3
|
|
| |
4
|
GilBert , E.N., and Pollak, H. Steiner minimal trees. SIAM J. Appl. Math. 16, (1968), 1-29.
|
| |
5
|
Graham, R.L. An efficient algorithm for determining the convex hull of a finite planar set, Inform. Proc. Lett. 1 (1972), 132-133.
|
| |
6
|
Grtinbaum, B. Convex Polytopes. Wiley Interscience, New York, 1967.
|
| |
7
|
Jarvis, R.A. On the identification of the convex hull of a finite set of points in the plane. Inform. Proc. Lett. 2, (1973), 18-21.
|
| |
8
|
|
| |
9
|
Shamos, M.I. Problems in computational geometry. Dep. Comptr. Sci., Yale U., New Haven, Conn., May 1975.
|
| |
10
|
Sklansky, J. Measuring concavity on a rectangular mosaic, IEEE Trans. Comptrs. C-21 (Dec. 1972), 1355-1364.
|
| |
11
|
Yao, F.F. On finding the maximal elements in a set of plane vectors. Comptr. Sci. Dep. Rep., U. of Illinois at Urbana- Champaign, Urbana, Ill., July 1974.
|
CITED BY 58
|
|
|
|
|
|
|
|
Timothy M. Chan, Output-sensitive results on convex hulls, extreme points, and related problems, Proceedings of the eleventh annual symposium on Computational geometry, p.10-19, June 05-07, 1995, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jon L. Bentley , Kenneth L. Clarkson , David B. Levine, Fast linear expected-time alogorithms for computing maxima and convex hulls, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.179-187, January 22-24, 1990, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
K. L. Clarkson , P. W. Shor, Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental, Proceedings of the fourth annual symposium on Computational geometry, p.12-17, June 06-08, 1988, Urbana-Champaign, Illinois, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hervé Brönnimann , John Iacono , Jyrki Katajainen , Pat Morin , Jason Morrison , Godfried Toussaint, Space-efficient planar convex hull algorithms, Theoretical Computer Science, v.321 n.1, p.25-40, June 16, 2004
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
James J. Little, Extended Gaussian images, mixed volumes, shape reconstruction, Proceedings of the first annual symposium on Computational geometry, p.15-23, June 05-07, 1985, Baltimore, Maryland, United States
|
|
|
|
|
|
Norm Dadoun , David G. Kirkpatrick , John P. Walsh, The geometry of beam tracing, Proceedings of the first annual symposium on Computational geometry, p.55-61, June 05-07, 1985, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sang Won Bae , Chunseok Lee , Hee-Kap Ahn , Sunghee Choi , Kyung-Yong Chwa, Computing minimum-area rectilinear convex hull and L-shape, Computational Geometry: Theory and Applications, v.42 n.9, p.903-912, November, 2009
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf