Quasi-optimal upper bounds for simplex range searching and new zone theorems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quasi-optimal upper bounds for simplex range searching and new zone theorems

Full text

Pdf (1.03 MB)

Source

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

Berkley, California, United States

Pages: 23 - 33

Year of Publication: 1990

ISBN:0-89791-362-0

Authors

Bernard Chazelle	Princeton University
Micha Sharir	New York University and Tel Aviv University
Emo Welzl	Free University, Berlin

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): 27, Citation Count: 15

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/98524.98532 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	Pankaj Kumar Agarwal , Micha Sharir, Intersection and decomposition algorithms for arrangements of curves in the plane, 1989
	2	B. Aronov , M. Sharir, Triangles in space or building (and analyzing) castles in the Air, Proceedings of the fourth annual symposium on Computational geometry, p.381-391, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73432]
	3	Chazelle, B. Lower bounds on the complexity of polytope range searching, J. Amer. Math. Soc. 2 (1989), 637-666.
	4	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.179-193, July 11-15, 1989
	5	Chazelle, B., Friedman, J. A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990).
	6	B. Chazelle , L. Palios, Triangulating a non-convex polytype, Proceedings of the fifth annual symposium on Computational geometry, p.393-400, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73876]
	7	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]
	8	Clarkson, K. Applications of random sampling in computational geometry, Disc. Comput. Geom. 2 (1987), 195-222.
	9	Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
	10	Clarkson, K., Edelsbrunner, H., Guibas, L.J., Sharir, M., Welzl, E. "Combinatorial complexity bounds for arrangements of curves and surfaces, Proc. 29th A.nn. IEEE Syrup. Found. Comput. Sci. (1988), 568-579.
	11	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	12	Richard Cole, Searching and sorting similar lists, Journal of Algorithms, v.7 n.2, p.202-220, June 1986 [doi>10.1016/0196-6774(86)90004-0]
	13	Richard Cole , Chee K Yap, Geometric retrieval problems, Information and Control, v.63 n.1-2, p.39-57, Oct/Nov. 1984 [doi>10.1016/S0019-9958(84)80040-6]
	14	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	15	Edelsbrunner, H. The upper envelope of piecewise linear functions: Tight bounds on the number of faces, Disc. Comput. Geom. 4 (1989), 337-343.
	16	H. Edelsbrunner , L. J. Guibas , J. Hershberger , R. Seidel , M. Sharir, Implicitly representing arrangements of lines or segments, Proceedings of the fourth annual symposium on Computational geometry, p.56-69, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73400]
	17	Edelsbrunner, H., Guibas, L.J., Sharir, M. The upper envelope of piecewise linear functions: Algorithms and applications, Disc. Comput. Geom. 4 (1989), 311-336.
	18	H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
	19	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
	20	Haussler, D., Welzl, E. Epsilon nets and simplex range queries, Disc. Comput. Geom. 2 (1987), 127- 151.
	21	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	22	Path, J., Sharir, M. The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates, Disc. Comput. Geom. 4 (1989), 291-309.
	23	Paterson, M., Yao, F.F. Point retrieval for polygons, J. Algorithms 7 (1986), 441--447.
	24	R. Pollack , M. Sharir , S. Sifrony, Separating two simple polygons by a sequence of translations, Discrete & Computational Geometry, v.3 n.2, p.123-136, Jan, 1988 [doi>10.1007/BF02187902]
	25	winard, D.E. Polygon retrieval, SIAM J. Comput. i1 (1982), 149-165.
	26	F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]
	27	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 15

	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
	Hervé Brönnimann , Bernard Chazelle, How hard is halfspace range searching?, Proceedings of the eighth annual symposium on Computational geometry, p.271-275, June 10-12, 1992, Berlin, Germany
	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
	David Eppstein , Jeff Erickson, Iterated nearest neighbors and finding minimal polytypes, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.64-73, January 25-27, 1993, Austin, Texas, United States
	Pankaj K. Agarwal , Micha Sharir, Ray shooting amidst convex polytopes in three dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.260-270, January 25-27, 1993, Austin, Texas, United States
	Pankaj K. Agarwal , Jiří Mataušek, Relative neighborhood graphs in three dimensions, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.58-65, 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
	Joseph S. B. Mitchell, Shortest paths among obstacles in the plane, Proceedings of the ninth annual symposium on Computational geometry, p.308-317, May 18-21, 1993, San Diego, California, United States
	Pankaj K. Agarwal , Marc van Kreveld , Mark Overmars, Intersection queries for curved objects (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.41-50, June 10-12, 1991, North Conway, New Hampshire, United States
	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
	Pankaj K. Agarwal , Micha Sharir, Counting circular arc intersections, Proceedings of the seventh annual symposium on Computational geometry, p.10-20, June 10-12, 1991, North Conway, New Hampshire, United States
	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
	Jiří Matoušek, Efficient partition trees, Proceedings of the seventh annual symposium on Computational geometry, p.1-9, June 10-12, 1991, North Conway, New Hampshire, United States
	Erin W. Chambers , Jeff Erickson , Pratik Worah, Testing contractibility in planar rips complexes, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA