Approximation algorithms for convex hulls

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximation algorithms for convex hulls

Full text

Pdf (574 KB)

Source

Communications of the ACM archive
Volume 25 , Issue 1 (January 1982) table of contents

Pages: 64 - 68

Year of Publication: 1982

ISSN:0001-0782

Authors

Jon Louis Bentley	Carnegie—Mellon Univ., Pittsburgh, PA
Franco P. Preparata	Univ. of Illinois, Urbana-Champaign
Mark G. Faust	Univ. of Illinois, Urbana-Champaign

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 71, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/358315.358392 What is a DOI?

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	Bentley, J.L. and Shamos, M.I. Divide and conquer for linear expected time. Information Processing Lett. 7, 2, (Feb. 1978), 87-91.
	2	Kevin Quentin Brown, Geometric transforms for fast geometric algorithms, 1979
	3	Devroye, L. A note on finding convex hulls via maximal vectors. Information Processing Letts. 11, 1, 53-56.
	4	Graham, R.L. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Lett. 1, 132-133.
	5	Lipton, R.J. and Tarjan, R.E. Application of a planar separator theorem. 18th Syrup. Foundations of Computer Science (Oct. 1977), IEEE, pp. 162-170.
	6	F. P. Preparata, An optimal real-time algorithm for planar convex hulls, Communications of the ACM, v.22 n.7, p.402-405, July 1979 [doi>10.1145/359131.359132]
	7	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	8	Michael Ian Shamos, Computational geometry., 1978
	9	Andrew C Yao, On constructing minimum spanning trees in k-dimensional spaces and related problems, Stanford University, Stanford, CA, 1977
	10	Andrew C Yao, A lower bound to finding convex hulls, Stanford University, Stanford, CA, 1979

CITED BY 5

	M. W. Bern , H. J. Karloff , P. Raghavan , B. Schieber, Fast geometric approximation techniques and geometric embedding problems, Proceedings of the fifth annual symposium on Computational geometry, p.292-301, June 05-07, 1989, Saarbruchen, West Germany
	Yossi Matias , Jeffrey Scott Vitter , Neal E. Young, Approximate data structures with applications, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.187-194, January 23-25, 1994, Arlington, Virginia, United States
	Mujtaba R. Ghouse , Michael T. Goodrich, In-place techniques for parallel convex hull algorithms (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.192-203, July 21-24, 1991, Hilton Head, South Carolina, United States
	Christian Ronse, A Bibliography on Digital and Computational Convexity (1961-1988), IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.181-190, February 1989
	Nikolay M. Sirakov, A New Active Convex Hull Model for Image Regions, Journal of Mathematical Imaging and Vision, v.26 n.3, p.309-325, December 2006