A Lower Bound to Finding Convex Hulls

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Lower Bound to Finding Convex Hulls

Full text

Pdf (383 KB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 4 (October 1981) table of contents

Pages: 780 - 787

Year of Publication: 1981

ISSN:0004-5411

Author

Andrew Chi-Chih Yao

Computer Science Department, Stanford University, Stanford, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 63, Citation Count: 9

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/322276.322289 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	Avis, D. On the complexity of finding the convex hull of a set of points. Tech. Rep. SOCS 79.2, McGdl Umverslty, Montreal, Ontano, Canada, 1979
	2	GRAHAM, R L An efficient algorithm for determining the convex hull of a t'mite set. Inf. Proc. Lea. 1 (1972), 132-133.
	3	SHAMOS, M.I. Computational geometry. Tech. Pep., Computer Science Dep., Carnegie-Mellon Umv., Pmsburgh, Pa, May 1978.
	4	VAN EMDE BOAS, P. On the f~(n log n) lower bound for convex hull and maxtmal vector determination. Inf. Proc. Left. 10 (1980), 132-136.
	5	Andrew C Yao, A lower bound to finding convex hulls, Stanford University, Stanford, CA, 1979

CITED BY 9

	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
	Shlomo Moran , Marc Snir , Udi Manber, Applications of Ramsey's theorem to decision tree complexity, Journal of the ACM (JACM), v.32 n.4, p.938-949, Oct. 1985
	S. B. Tor , A. E. Middleditch, Convex Decomposition of Simple Polygons, ACM Transactions on Graphics (TOG), v.3 n.4, p.244-265, Oct. 1984
	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States
	Jeff Erickson, New lower bounds for convex hull problems in odd dimensions, Proceedings of the twelfth annual symposium on Computational geometry, p.1-9, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Sandeep Sen , Neelima Gupta, Distribution-sensitive algorithms, Nordic Journal of Computing, v.6 n.2, p.194-211, Summer 1999
	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
	Fadi Yaacoub , Yskandar Hamam , Antoine Abche, A 3D Convex Hull algorithm for modelling medical data in a virtual environment, International Journal of Intelligent Systems Technologies and Applications, v.5 n.1/2, p.3-19, May 2008