Intersection queries for curved objects (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Intersection queries for curved objects (extended abstract)

Full text

Pdf (889 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: 41 - 50

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Pankaj K. Agarwal	Computer Science Department, Duke University, Durham, NC
Marc van Kreveld	Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands
Mark Overmars	Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands

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): 16, Citation Count: 0

Additional Information:

references 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.109653 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	P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, Proceedings of the fifth annual symposium on Computational geometry, p.315-325, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73868]
	2	P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its application, Proceedings of the fifth annual symposium on Computational geometry, p.11-22, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73835]
	3	Agarwal, P. K., M. van Kreveld, and M. Overmars, Intersection Queries for Curved Objects, manuscript. 1990.
	4	P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
	5	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]
	6	Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
	7	Chazelle, B., H. Edelsbrunner, M. Grigni, L. Guibas, M. Shark, and J. Snoeyink, Ray Shooting in Polygons Using Geodesic Triangulations, manuscript, 1990.
	8	Chazelle, B., and L. J. Guibas, Fractional cascading: I. A data structuring technique, Algorithmica I (1986), pp. 133-162.
	9	Chazelle, B., and L. J. Guibas, Fractional cascading: II. Applications, Algorithmica 1 (1986), pp. 163-191.
	10	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]
	11	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]
	12	David P. Dobkin , Herbert Edelsbrunner, Space searching for intersecting objects, Journal of Algorithms, v.8 n.5, p.348-361, Sept. 1987 [doi>10.1016/0196-6774(87)90015-0]
	13	James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
	14	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	15	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
	16	Guibas, L., M. Overmars, and M. Sharir, Ray shooting, implicit point location, and related queries in arrangements of segments, Techn. Rep. No. 433, New York University, 1989.
	17	Haussler, D., and E. Welzl, c-nets and simplex range queries, Discr. & Comp. Geom. 2 (1987), pp. 127-151.
	18	M. van Kreveld , M. Overmars , P. K. Agarwal, Intersection queries in sets of disks, Proceedings of the second Scandinavian workshop on Algorithm theory, p.393-403, July 1990, Bergen, Sweden
	19	Matou~ek, J., More on cutting arrangements and spanning trees with low crossing number, Techn. ReD. B-90-02, Freie Universit~ Berlin, 1990.
	20	J. Matoušek , E. Welzl, Good splitters for counting points in triangles, Proceedings of the fifth annual symposium on Computational geometry, p.124-130, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73847]
	21	M. H. Overmars , H. Schipper , M. Sharir, Storing line segments in partition trees, BIT, v.30 n.3, p.385-403, 1990 [doi>10.1007/BF01931656]
	22	Sharir, M., The k-set problem for arrangements of curves and surfaces, to appear in Discr. & Comp. Geom.
	23	Snoeyink, J., private communication.
	24	Willard, D. E., Polygon retrieval, SIAM J. Comput. 11 (1982), pp. 149-165.
	25	F. Frances Yao , David P. Dobkin , Herbert Edelsbrunner , Michael S. Paterson, Partitioning space for range queries, SIAM Journal on Computing, v.18 n.2, p.371-384, April 1989 [doi>10.1137/0218025]