Output-size sensitive algorithms for finding maximal vectors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Output-size sensitive algorithms for finding maximal vectors

Full text

Pdf (687 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the first annual symposium on Computational geometry table of contents

Baltimore, Maryland, United States

Pages: 89 - 96

Year of Publication: 1985

ISBN:0-89791-163-6

Authors

David G. Kirkpatrick	Computer Science Department, Univemity of British Columbia, Vancouver, B.C. V6T lW5, Canada
Raimund Seidel	Computer Science Department, Cornell University, Ithaca NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 19, Citation Count: 2

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/323233.323246 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
	3	[BS] J. L. Bentley and M. I. Shamos: Divide and Conquer for Linear Expected Time. Information Processing Letters 7, (1978) 87-91.
	4	J. L. Bentley , H. T. Kung , M. Schkolnick , C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM (JACM), v.25 n.4, p.536-543, Oct. 1978 [doi>10.1145/322092.322095]
	5	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
	6	[KS] D. G. Kirkpatrick and R. Seidel: The Ultimate Planar Convex Hull Algorithm? Cornell CS Tech. Rep. 83-577; to appear in SIAM J. on Computing.
	7	H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
	8	[R] P. Ramanan: Private Communication.

CITED BY 2

	Oswin Aichholzer , Danny Z. Chen , D. T. Lee , Asish Mukhopadhyay , Evanthia Papadopoulou , Franz Aurenhammer, Voronoi diagrams for direction-sensitive distances, Proceedings of the thirteenth annual symposium on Computational geometry, p.418-420, June 04-06, 1997, Nice, France
	Sandeep Sen , Neelima Gupta, Distribution-sensitive algorithms, Nordic Journal of Computing, v.6 n.2, p.194-211, Summer 1999