On range reporting, ray shooting and k-level construction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On range reporting, ray shooting and k-level construction

Full text

Pdf (1.13 MB)

Source

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

Miami Beach, Florida, United States

Pages: 390 - 399

Year of Publication: 1999

ISBN:1-58113-068-6

Author

Edgar A. Ramos

Max-Planck-Institut für Informatik, D-66123 Saarbrücken, Germany

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): 26, Citation Count: 13

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/304893.304993 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 K. Agarwal , Mark de Berg , Jirí Matousek , Otfried Schwarzkopf, Constructing Levels in Arrangements and Higher Order Voronoi Diagrams, SIAM Journal on Computing, v.27 n.3, p.654-667, June 1998 [doi>10.1137/S0097539795281840]
	2	P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. To appear in Discrete and Computational Geometry: Ten Years Later (B. Chazelle, J. E. Goodman, and R. Pollack, eds.) AMS Press.
	3	Pankaj K. Agarwal , Jirí Matousek , Otfried Schwarzkopf, Computing Many Faces in Arrangements of Lines and Segments, SIAM Journal on Computing, v.27 n.2, p.491-505, April 1998 [doi>10.1137/S009753979426616X]
	4	Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Computing faces in segment and simplex arrangements, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.672-682, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225285]
	5	M. de Berg, K. Dobrindt and O. Schwarzkopf. On lazy randomized incremental construction. Discrete Comput. Geom. 14 (1995), 261-286.
	6	Herve Bronnimann, Derandomization of geometric algorithms, Princeton University, Princeton, NJ, 1995
	7	H. BrSnnimann, B. Chazelle and J. Matou~ek. Product range spaces, sensitive sampling, and derandomization. FOCS'93, 400-409.
	8	Timothy M. Chan, Fixed-dimensional linear programming queries made easy, Proceedings of the twelfth annual symposium on Computational geometry, p.284-290, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237397]
	9	Timothy M. Chan, Random Sampling, Halfspace Range Reporting, and Construction of (= k)-Levels in Three Dimensions, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.586, November 08-11, 1998
	10	Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
	11	B. Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom., 10 (1993), 377-409.
	12	B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatot/ca, 10 (1990), 229-249.
	13	Bernard Chazelle , Joel Friedman, Point location among hyperplanes and unidirectional ray-shooting, Computational Geometry: Theory and Applications, v.4 n.2, p.53-62, June 1994 [doi>10.1016/0925-7721(94)90009-4]
	14	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]
	15	A. Crauser , P. Ferragina , K. Mehlhorn , U. Meyer , E. Ramos, Randomized external-memory algorithms for some geometric problems, Proceedings of the fourteenth annual symposium on Computational geometry, p.259-268, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276914]
	16	Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
	17	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Journal of Computer and System Sciences, v.50 n.2, p.203-208, April 1995
	18	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	19	Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
	20	Jiří Matoušek, On vertical ray shooting in arrangements, Computational Geometry: Theory and Applications, v.2 n.5, p.279-285, March 1993 [doi>10.1016/0925-7721(93)90024-Z]
	21	J. Matougek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Cornput. Geom. 10 (1993), 215-232.
	22	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1993.

CITED BY 13

	Timothy M. Chan, Dynamic planar convex hull operations in near-logarithmic amortized time, Journal of the ACM (JACM), v.48 n.1, p.1-12, Jan. 2001
	Joachim Gudmundsson , Herman J. Haverkort , Marc van Kreveld, Constrained higher order Delaunay triangulations, Computational Geometry: Theory and Applications, v.30 n.3, p.271-277, March 2005
	Joachim Gudmundsson , Mikael Hammar , Marc van Kreveld, Higher order Delaunay triangulations, Computational Geometry: Theory and Applications, v.23 n.1, p.85-98, July 2002
	Haim Kaplan , Micha Sharir, Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.484-493, January 22-26, 2006, Miami, Florida
	Timothy M. Chan, A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1196-1202, January 22-26, 2006, Miami, Florida
	Peyman Afshani , Timothy M. Chan, On approximate range counting and depth, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Thierry de Kok , Marc van Kreveld , Maarten Löffler, Generating realistic terrains with higher-order Delaunay triangulations, Computational Geometry: Theory and Applications, v.36 n.1, p.52-65, January 2007
	Marc Benkert , Joachim Gudmundsson , Herman Haverkort , Alexander Wolff, Constructing minimum-interference networks, Computational Geometry: Theory and Applications, v.40 n.3, p.179-194, August, 2008
	David Bremner , Dan Chen , John Iacono , Stefan Langerman , Pat Morin, Output-sensitive algorithms for Tukey depth and related problems, Statistics and Computing, v.18 n.3, p.259-266, September 2008
	Peyman Afshani , Timothy M. Chan, Optimal halfspace range reporting in three dimensions, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.180-186, January 04-06, 2009, New York, New York
	Peyman Afshani , Chris Hamilton , Norbert Zeh, A general approach for cache-oblivious range reporting and approximate range counting, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Peyman Afshani , Chris Hamilton , Norbert Zeh, Cache-oblivious range reporting with optimal queries requires superlinear space, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Bernard Chazelle , Wolfgang Mulzer, Computing hereditary convex structures, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark