Dynamic trees and dynamic point location

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamic trees and dynamic point location

Full text

Pdf (1.07 MB)

Source

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

New Orleans, Louisiana, United States

Pages: 523 - 533

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Michael T. Goodrich	The Johns Hopkins Univ., Baltimore, MD
Roberto Tamassia	Brown Univ., Providence, RI

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 30, Citation Count: 18

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/103418.103472 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	J.L. Bentley and D. Wood, "An Optimal Worst Case Algorithm for Repotting Intersections of Rectangles," IEEE Trans. on Computers, C- 29(7), 1980, 571-576.
	2	B. Chazelle, "A theorem on polygon cutting with applications," 23rd FOCS, 339-349, 1982.
	3	B. Chazelle, "Triangulating a Simple Polygon in Linear Time," Report CS-TR-264-90, Princeton University, May 1990. (Prelim. version: 31st FOCS, 220-230, 1990.)
	4	B. Chazelle and L.J. Guibas, "Fractional Cascading: I. A Data Structuring Technique," Algorith. mica, 1(2), 133-162, 1986.
	5	Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
	6	Yi-Jen Chiang , Roberto Tamassia, Dynamization of the trapezoid method for planar point location (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.61-70, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109655]
	7	S.W. Cheng and R. Janardan, "New Results on Dynamic Planar Point Location," Technical Report TR 90-13, Dept. of Computer Science, Univ. of Minnesota, 1990. (Prelim. version" 31st FOCS, 96-105, 1990.)
	8	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]
	9	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	10	Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
	11	David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook , Moti Yung, Maintenance of a minimum spanning forest in a dynamic planar graph, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.1-11, January 22-24, 1990, San Francisco, California, United States
	12	O. Fries, "Zerlegung ether planaren Unterteilung der Ebene und ihre Anwendungen," M.S. thesis, Inst. Angew. Math. and Inform., Univ. Saarlandes, Saarbrcken, Germany, 1985.
	13	O. Fries , K. Mehlhorn , St. Näher, Dynamization of geometric data structures, Proceedings of the first annual symposium on Computational geometry, p.168-176, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323256]
	14	L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10516]
	15	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	16	D. Kirkpatrick, "Optimal Search in Planar Subdivision," SIAM Journal on Computing, Vol. 12, No. 1, February 1983, pp. 28-35.
	17	D.T. Lee and F.P. Preparata, "Location of a Point in a Planar Subdivision and its Applications," SIAM J. Computing, Vol. 6, No. 3, 594-606, 1977.
	18	D.T. Lee and F.P. Preparata, "Computational GeometrywA Survey," IEEE Trans. on Computers, Vol. C-33, No. 12, December 1984, pp. 872- 1101.
	19	C. Levcopoulos , Mark H. Overmars, A balanced search tree with O(1) worst case update time, Acta Informatica, v.26 n.3, p.269-277, Nov. 1988 [doi>10.1007/BF00299635]
	20	E.M. McCreight, "Priority Search Trees," SIAM J. on Comput., No. 14, 1985, 257-276.
	21	K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Springer-Verlag, 1984.
	22	Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	23	Mark H. Overmars, Range searching in a set of line segments, Proceedings of the first annual symposium on Computational geometry, p.177-185, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323257]
	24	F.P. Preparata, "A New Approach to Planar Point Location," SIAM J. Computing, Vol. 10, No. 3, 1981, 73-83.
	25	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	26	Franco P. Preparata , Roberto Tamassia, Fully dynamic point location in a monotone subdivision, SIAM Journal on Computing, v.18 n.4, p.811-830, Aug. 1989 [doi>10.1137/0218056]
	27	Franco P. Preparata , Roberto Tamassia, Efficient Spatial Point Location (Extended Abstract), Proceedings of the Workshop on Algorithms and Data Structures, p.3-11, August 17-19, 1989
	28	Franco P. Preparata , Roberto Tamassia, Dynamic planar point location with optimal query time, Theoretical Computer Science, v.74 n.1, p.95-114, July 30, 1990
	29	Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
	30	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	31	Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]

CITED BY 18

	David Eppstein, Average case analysis of dynamic geometric optimization, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.77-86, January 23-25, 1994, Arlington, Virginia, United States
	Michael T. Goodrich, Planar separators and parallel polygon triangulation (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.507-516, May 04-06, 1992, Victoria, British Columbia, Canada
	Michael T. Goodrich , Mark Orletsky , Kumar Ramaiyer, Methods for achieving fast query times in point location data structures, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.757-766, January 05-07, 1997, New Orleans, Louisiana, United States
	Marc de Berg , Leonidas J. Guibas , Dan Halperin, Vertical decompositions for triangles in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.1-10, June 06-08, 1994, Stony Brook, New York, United States
	R. F. Cohen , G. Di Battista , R. Tamassia , I. G. Tollis , P. Bertolazzi, A framework for dynamic graph drawing, Proceedings of the eighth annual symposium on Computational geometry, p.261-270, June 10-12, 1992, Berlin, Germany
	Yi-Jen Chiang , Franco P. Preparata , Roberto Tamassia, A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.44-53, January 25-27, 1993, Austin, Texas, United States
	Hanna Baumgarten , Hermann Jung , Kurt Mehlhorn, Dynamic point location in general subdivisions, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.250-258, September 1992, Orlando, Florida, United States
	Yi-Jen Chiang , Joseph S. B. Mitchell, Two-point Euclidean shortest path queries in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.215-224, January 17-19, 1999, Baltimore, Maryland, United States
	Piotr Berman , Zheng Zhang , Yuri I. Wolf , Eugene V. Koonin , Webb Miller, Winnowing sequences from a database search, Proceedings of the third annual international conference on Computational molecular biology, p.50-58, April 11-14, 1999, Lyon, France
	Yi-Jen Chiang , Roberto Tamassia, Dynamization of the trapezoid method for planar point location (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.61-70, June 10-12, 1991, North Conway, New Hampshire, United States
	Marco Pellegrini, On point location and motion planning among simplices, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.95-104, May 23-25, 1994, Montreal, Quebec, Canada
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Michael T. Goodrich , Joseph S. B. Mitchell , Mark W. Orletsky, Practical methods for approximate geometric pattern matching under rigid motions: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.103-112, June 06-08, 1994, Stony Brook, New York, United States
	Cláudio T. Silva , Joseph S. B. Mitchell , Peter L. Williams, An exact interactive time visibility ordering algorithm for polyhedral cell complexes, Proceedings of the 1998 IEEE symposium on Volume visualization, p.87-94, October 19-20, 1998, Research Triangle Park, North Carolina, United States
	Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths via balanced geodesic triangulations, Proceedings of the ninth annual symposium on Computational geometry, p.318-327, May 18-21, 1993, San Diego, California, United States
	Mikhail J. Atallah , Michael T. Goodrich , Kumar Ramaiyer, Biased finger trees and three-dimensional layers of maxima: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.150-159, June 06-08, 1994, Stony Brook, New York, United States
	Peter L. Williams, Visibility-ordering meshed polyhedra, ACM Transactions on Graphics (TOG), v.11 n.2, p.103-126, April 1992
	Erik D. Demaine , John Iacono , Stefan Langerman, Retroactive data structures, ACM Transactions on Algorithms (TALG), v.3 n.2, p.13-es, May 2007