Ray shooting and parametric search

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Ray shooting and parametric search

Full text

Pdf (1.07 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 517 - 526

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Pankaj K. Agarwal	Computer Science Department, Duke University, Durham, NC
Jiří Matoušek	Department of Applied Mathematics, Charles University, Praha

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 66, Citation Count: 22

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/129712.129763 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, Ray shooting and other applications of spanning trees with low stabbing number, SIAM Journal on Computing, v.21 n.3, p.540-570, June 1992 [doi>10.1137/0221035]
	2	K P Agarwal , Jiri Matousek, Ray Shooting and Parametric Search, Duke University, Durham, NC, 1991
	3	K P Agarwal , Jiri Matousek, Dynamic Half-Space Range Reporting and Its Application, Duke University, Durham, NC, 1991
	4	P. K. Agarwal and M. Sharir, Planar geometric location problems, Tech. Rept. 90-58, DIMACS, Rutgers University, August 1990. (Also to appear in Algorithmica.)
	5	P. K. Agarwal and M. Sharix, Applications of a new partitioning scheme, Proc. 2nd Workshop on Algorithms and Data Structures, 1991, pp. 379-392.
	6	Boris Aronov , Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Rephael Wenger, Points and triangles in the plane and halving planes in space, Discrete & Computational Geometry, v.6 n.5, p.435-442, 1991 [doi>10.1007/BF02574700]
	7	M. de Berg , D. Halperin , M. Overmars , J. Snoeyink , M. van Kreveld, Efficient ray shooting and hidden surface removal, Proceedings of the seventh annual symposium on Computational geometry, p.21-30, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109651]
	8	M. de Berg and M. Overmars, Hidden Surface Removal for Axis-Parallel Polyhedra, Proceedings 31"t Annual 1EEE Symposium on Foundations of Computer Science, 1990, pp. 252-261.
	9	B. Chazelle, On the convex layers of a planar set, IEEE Trans. Information Theory IT-31 (1985), 509- 517.
	10	B. Chazelle , H. Edelsbrunner , L. Guibas , M. Sharir, Lines in space-combinators, algorithms and applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.382-393, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73044]
	11	B. Chazelle , L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete & Computational Geometry, v.4 n.6, p.551-581, Sep. 1989 [doi>10.1007/BF02187747]
	12	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]
	13	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]
	14	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]
	15	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]
	16	Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
	17	David P. Dobkin , David G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.400-413, July 1990, Warwick University, England
	18	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	19	H. Edelsbrunner and E. Welzl, Constructing belts in two-dimensional arrangements with applications, SIAM J. Computing 15 (1986), 271-284.
	20	L. Guibas, M. Overmars and M. Sharir, Ray shooting, impficit point location, and related queries in arrangements of segments, Tech. Report 433, Courant Institute, New York University, 1989.
	21	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 [doi>10.1145/109648.109649]
	22	Jiří Matoušek, Reporting points in halfspaces, Proceedings of the 32nd annual symposium on Foundations of computer science, p.207-215, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185370]
	23	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 [doi>10.1145/142675.142732]
	24	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 [doi>10.1145/142675.142683]
	25	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	26	Ketan Mulmuley, On levels in arrangements and Voronoi diagrams, Discrete & Computational Geometry, v.6 n.4, p.307-338, 1991 [doi>10.1007/BF02574692]
	27	Ketan Mulmuley, Randomized multidimensional search trees: further results in dynamic sampling (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.216-227, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185371]
	28	M. Overmars and M. Sharir, Output-sensitive hidden surface removal, Proc. 30th 1EEE Syrup. on Foundations of Computer Science, 1989, pp. 598- 603.
	29	J. Pach, W. Steiger, and E. Szemer#di, An upper bound on the number of planar k-sets, Proc. 30th 1EEE Symposium on Foundations of Computer Science, 1989, pp. 72-79.
	30	O. Schwarzkopf. Ray shooting in convex polytopes. Technical Report B-91-18, FB Mathematik, Freie Universit#t Berlin, 1991.
	31	D. Sommerville, Analytical Geometry in Three Dimensions, Cambridge, 1951.
	32	S. Vre6ica and R. 2ivaljevi6, The colored Tverberg's problem and complexes of injective functions, Manuscript, 1991.

CITED BY 22

	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
	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
	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States
	Omer Barkol , Yuval Rabani, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Journal of Computer and System Sciences, v.64 n.4, p.873-896, June 2002
	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
	Elmar Schömer , Christian Thiel, Efficient collision detection for moving polyhedra, Proceedings of the eleventh annual symposium on Computational geometry, p.51-60, June 05-07, 1995, Vancouver, British Columbia, Canada
	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
	Marco Pellegrini, On lines missing polyhedral sets in 3-space, Proceedings of the ninth annual symposium on Computational geometry, p.19-28, May 18-21, 1993, San Diego, California, United States
	Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, 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
	Mark de Berg, Generalized hidden surface removal, Proceedings of the ninth annual symposium on Computational geometry, p.1-10, May 18-21, 1993, San Diego, California, United States
	Piotr Indyk , Rajeev Motwani , Prabhakar Raghavan , Santosh Vempala, Locality-preserving hashing in multidimensional spaces, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.618-625, May 04-06, 1997, El Paso, Texas, United States
	Matthew J. Katz , Micha Sharir, An expander-based approach to geometric optimization, Proceedings of the ninth annual symposium on Computational geometry, p.198-207, May 18-21, 1993, San Diego, California, United States
	Michael T. Goodrich, Efficient piecewise-linear function approximation using the uniform metric: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.322-331, June 06-08, 1994, Stony Brook, New York, United States
	Ding Liu, A strong lower bound for approximate nearest neighbor searching, Information Processing Letters, v.92 n.1, p.23-29, 16 October 2004
	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States
	A. M. Roumani , D. B. Skillicorn, Mobile services discovery and selection in the publish/subscribe paradigm, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.163-173, October 04-07, 2004, Markham, Ontario, Canada
	Rina Panigrahy, Entropy based nearest neighbor search in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1186-1195, January 22-26, 2006, Miami, Florida
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Lower bounds for high dimensional nearest neighbor search and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.312-321, May 01-04, 1999, Atlanta, Georgia, United States
	Omer Barkol , Yuval Rabani, Tighter bounds for nearest neighbor search and related problems in the cell probe model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.388-396, May 21-23, 2000, Portland, Oregon, United States