Dynamization of the trapezoid method for planar point location (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamization of the trapezoid method for planar point location (extended abstract)

Full text

Pdf (806 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: 61 - 70

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Yi-Jen Chiang	Department of Computer Science, Brown University, Providence, R. I.
Roberto Tamassia

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): 5, Downloads (12 Months): 27, Citation Count: 6

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/109648.109655 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	S.W. Bent, D.D. Sleator, and R.E. Tarjan, "Biased Search Trees," SIAM J. Computing, vol. 14, 545- 568, 1985.
	2	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 FOC$, 96- 105, 1990.)
	3	Yi Chiang , Roberto Tamassia, Dynamic Algorithms in Computational Geometry, Brown University, Providence, RI, 1991
	4	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]
	5	O. Fries, "Zerlegung einer planaren Unterteilung der Ebene und ihre Anwendungen," M.S. thesis, Inst. Angew. Math. and Inform., Univ. Saarlandes, Saarbrcken, Germany, 1985.
	6	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]
	7	Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103472]
	8	D. Kirkpatrick, "Optimal Search in Planar Subdivision,'' SIAM Journal on Computing, Vol. 12, 28-35, 1983.
	9	D.T. Lee and F.P. Preparata, "Location of a Point in a Planar Subdivision and its Applications," SIAM J. Computing, Vol. 6, 594-606, 1977.
	10	E.M. McCreight, "Priority Search Trees," SIAM J. on Comput., Vol. 14, 257-276, 1985.
	11	K. Mehlhorn, Data Structure and Algorithms 1: Sorting and Searching, 189-199, 1984.
	12	M. H. Overmars and J. van Leeuwen, "Maintenance of Configurations in the Plane," J. Compt. and $yst. Sci., Vol. 23, 166-204, 1981.
	13	Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	14	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]
	15	F.P. Preparata, "A New Approach to Planar Point Location," SIAM J. Computing, Vol. 10, 473-483, 1981.
	16	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	17	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]
	18	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
	19	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]
	20	Roberto Tamassia, An incremental reconstruction method for dynamic planar point location, Information Processing Letters, v.37 n.2, p.79-83, Jan. 31, 1991 [doi>10.1016/0020-0190(91)90138-8]

CITED BY 6

	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
	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 , 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
	Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, 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
	Christian Icking , Rolf Klein , Peter Köllner , Lihong Ma, Java applets for the dynamic visualization of Voronoi diagrams, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003