Efficient partition trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient partition trees

Full text

Pdf (938 KB)

Source

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

North Conway, New Hampshire, United States

Pages: 1 - 9

Year of Publication: 1991

ISBN:0-89791-426-0

Author

Jiří Matoušek

Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czechoslovakia

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): 4, Downloads (12 Months): 38, Citation Count: 14

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/109648.109649 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.

	Agarwal 90	Pankaj K. Agarwal, Partitioning arrangements of lines, part I: an efficient deterministic algorithm, Discrete & Computational Geometry, v.5 n.5, p.449-483, 1990 [doi>10.1007/BF02187805]
	Aggarwal et al. 90	A. Aggarwal , M. Hansen , T. Leighton, Solving query-retrieval problems by compacting Voronoi diagrams, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.331-340, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100260]
	Bentley 79	J. L. Bentley. Decomposable searching problems. Information Processing Letters 8:244-251, 1979.
	Chazelle 89	B. Chazelle. Lower bounds on the complexity of polytope range searching. J. Amer. Math. Soc, 2(4):637- 666, 1989.
	Chazelle et al. 85	Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
	Chazelle et al. 90	Bernard Chazelle , Micha Sharir , Emo Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Proceedings of the sixth annual symposium on Computational geometry, p.23-33, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98532]
	Chazelle,Friedman 90	B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10,3:229-249, 1990.
	Chazelle,Preparata 86	B. Chazelle , F. P. Preparata, Halfspace range search: an algorithmic application of k-sets, Discrete & Computational Geometry, v.1 n.1, p.83-93, 1986 [doi>10.1007/BF02187685]
	Chazelle,Welzl 89	B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
	Edelsbrunner,Welzl 86	H Edelsbrunner , E Welzl, Halfplanar range search in linear space and O(n0.695) query time, Information Processing Letters, v.23 n.6, p.289-293, Dec. 3, 1986
	Haussler,Welzl 87	D. Haussler and E. Welzl. e-nets and simplex range queries. Discrete ~ Comptltotional Geometry, 2:127- 151, 1987.
	Matou&sbreve;ek 90a	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
	Matou&sbreve;ek 90b	Jiří Matoušek, Cutting hyperplane arrangements, Proceedings of the sixth annual symposium on Computational geometry, p.1-9, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98528]
	Matou&sbreve;ek 90c	J. Matou~ek. More on cutting arrangements and spanning trees with low crossing number. Tech. Report B-90-2, FU Berlin, FB Mathematik, 1990.
	Overmars 83	Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	Schipper,Overmars 90	H. Schipper , M. H. Overmars, Dynamic partition trees, Proceedings of the second Scandinavian workshop on Algorithm theory, p.404-417, July 1990, Bergen, Sweden
	Vapnik,Chervonenkis 71	V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264-280, 1971.
	Welzl 88	E. Welzl, Partition trees for triangle counting and other range searching problems, Proceedings of the fourth annual symposium on Computational geometry, p.23-33, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73397]
	Willard 82	D. E. Willard. Polygon retrieval. SIAM Journal on Computing, 11:149-165, 1982.
	Yao,Yao 85	A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]

CITED BY 14

	Marco Pellegrini, Incidence and nearest-neighbor problems for lines in 3-space, Proceedings of the eighth annual symposium on Computational geometry, p.130-137, June 10-12, 1992, Berlin, Germany
	Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany
	Otfried Schwarzkopf, Ray shooting in convex polytopes, Proceedings of the eighth annual symposium on Computational geometry, p.286-295, June 10-12, 1992, Berlin, Germany
	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.517-526, May 04-06, 1992, Victoria, British Columbia, Canada
	Mark de Berg , Mark Overmars , Otfried Schwarzkopf, Computing and verifying depth orders, Proceedings of the eighth annual symposium on Computational geometry, p.138-145, June 10-12, 1992, Berlin, Germany
	Takeshi Tokuyama, Minimax parametric optimization problems and multi-dimensional parametric searching, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.75-83, July 2001, Hersonissos, Greece
	Jiří Matoušek , Otfried Schwarzkopf, Linear optimization queries, Proceedings of the eighth annual symposium on Computational geometry, p.16-25, June 10-12, 1992, Berlin, Germany
	Jiří Matoušek , David M. Mount , Nathan S. Netanyahu, Efficient randomized algorithms for the repeated median line estimator, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.74-82, January 25-27, 1993, Austin, Texas, United States
	Boris Aronov , Paul Erdős , Wayne Goddard , Daniel J. Kleitman , Michael Klugerman , János Pach , Leonard J. Schulman, Crossing families, Proceedings of the seventh annual symposium on Computational geometry, p.351-356, June 10-12, 1991, North Conway, New Hampshire, United States
	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
	Jiří Matoušek, Range searching with efficient hierarchical cuttings, Proceedings of the eighth annual symposium on Computational geometry, p.276-285, June 10-12, 1992, Berlin, Germany
	Prosenjit Bose , David Bremner , Marc van Kreveld, Determining the castability of simple polyhedra, Proceedings of the tenth annual symposium on Computational geometry, p.123-131, June 06-08, 1994, Stony Brook, New York, United States
	Takeshi Tokuyama, Efficient algorithms for the minimum diameter bridge problem, Computational Geometry: Theory and Applications, v.24 n.1, p.11-18, January 2003