Dynamization of geometric data structures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamization of geometric data structures

Full text

Pdf (706 KB)

Source

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

Baltimore, Maryland, United States

Pages: 168 - 176

Year of Publication: 1985

ISBN:0-89791-163-6

Authors

O. Fries	Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West Germany
K. Mehlhorn	Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West Germany
St. Näher	Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West 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): 19, Citation Count: 12

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/323233.323256 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	[1] B. Chazelle, L. Guibas: "Fractional Cascading" ICALP 85, to appear.
	2	[2] H. Edelsbrunner, L. J. Guibas, I. Stolfi: "Optimal Point Location in a Monotone Subdivision" DEC System Research Report No. 2, Palo Alto.
	3	[3] S. Huddleston, K. Mehlhorn: "A new Representation for Linear Lists" Acta Informatica 17, 157-184 (1982).
	4	[4] H. Imai, T. Asano: "Dynamic Segment Intersection with Applications" 25th FOCS 1984, 393-402.
	5	[5] D. Kirkpatrick: "Optimal Search in Planar Subdivisions" SICOMP 12 (1983), 28-35.
	6	[6] R. Lipton, R. E. Tarjan: "Applications of a Planar Separator Theorem" 18th FOCS, 1977, 162-170.
	7	[7] D. T. Lee, F. P. Preparata: "Location of a Point in a Planar Subdivision and its Applications" SIAM J. of Computing, Vol 6, no 3, 1977, 594-606.
	8	[8] G. S. Lueker: "A Data Structure for Orthogonal Range Queries" 19th FOCS, 1978, 28-34.
	9	[9] D. Maier, S. C. Salveter: "Hysterical B-Trees" Stony Brook, cs Dep. TR #79/007.
	10	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	11	[11] V. K. Vaishnavi, D. Wood: "Rectilinear Line Segment Intersection, Layered Segment Trees, and Dynamization" Journal of Algorithms, Vol 3 (1982), 160-176.
	12	Dan E. Willard, New data structures for orthogonal range queries, SIAM Journal on Computing, v.14 n.1, p.232-253, Feb. 1985 [doi>10.1137/0214019]
	13	[13] D. E. Willard: "New Data Structures for Orthogonal Range Queries" Technical Report, Harvard University, 1978.
	14	[14] P. v. Emde Boas, R. Kaas, E. Zijlstra: "Design and Implementation of an efficient priority queue" Math. Systems Theory, 10, 1977, 99-127.
	15	[15] W. Lipski: "Finding a Manhattan Path and Related Problems" Networks 13, 1983, 399-409.

CITED BY 12

	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
	D E Willard, On the application of sheared retrieval to orthogonal range queries, Proceedings of the second annual symposium on Computational geometry, p.80-89, June 02-04, 1986, Yorktown Heights, New York, 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
	Dan E. Willard, Quasilinear algorithms for processing relational calculus expressions (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.243-257, April 02-04, 1990, Nashville, Tennessee, United States
	T. Tamassia , J. S. Vitter, Optimal cooperative search in fractional cascaded data structures, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.307-316, July 02-06, 1990, Island of Crete, Greece
	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
	Ketan Mulmuley , Sandeep Sen, Dynamic point location in arrangements of hyperplanes, Proceedings of the seventh annual symposium on Computational geometry, p.132-141, June 10-12, 1991, North Conway, New Hampshire, 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
	Franco P. Preparata , Jeffrey S. Vitter , Mariette Yvinec, Computation of the axial view of a set of isothetic parallelepipeds, ACM Transactions on Graphics (TOG), v.9 n.3, p.278-300, July 1990
	M. Bern, Hidden surface removal for rectangles, Proceedings of the fourth annual symposium on Computational geometry, p.183-192, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Ketan Mulmuley, Randomized multidimensional search trees (extended abstract): dynamic sampling, Proceedings of the seventh annual symposium on Computational geometry, p.121-131, June 10-12, 1991, North Conway, New Hampshire, United States
	Dan E. Willard, Multidimensional search trees that provide new types of memory reductions, Journal of the ACM (JACM), v.34 n.4, p.846-858, Oct. 1987