Union-copy structures and dynamic segment trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Union-copy structures and dynamic segment trees

Full text

Pdf (1.20 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 3 (July 1993) table of contents

Pages: 635 - 652

Year of Publication: 1993

ISSN:0004-5411

Authors

Marc J. van Kreveld	Utrecht University, Utrecht, the Netherlands
Mark H. Overmars	Utrecht University, Utrecht, the Netherlands

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 53, Citation Count: 4

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/174130.174140 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Bruce W. Arden , Bernard A. Galler , Robert M. Graham, An algorithm for equivalence declarations, Communications of the ACM, v.4 n.7, p.310-314, July 1961 [doi>10.1145/366622.366626]
	3	~BENTLEY, J.L. Solutzons to Klee's Rectangle Problems, unpublished notes. Dept. of Comput. Scl., Carnegie-Mellon Umv., Pittsburgh, Pa., 1977.
	4	Norbert Blum, On the single-operation worst-case time complexity of the disjoint set union problem, SIAM Journal on Computing, v.15 n.4, p.1021-1024, Nov. 1986 [doi>10.1137/0215072]
	5	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]
	6	~GABOW, n. N., AND TARJAN, R.E. A linear-nine algorithm for a specml case of disjoint set union. J. Comput. Syst. Sct. 30 (lC;85), 209-221.
	7	Benrard A. Galler , Michael J. Fisher, An improved equivalence algorithm, Communications of the ACM, v.7 n.5, p.301-303, May 1964 [doi>10.1145/364099.364331]
	8	~GOLUMBIC, M. C. Algorithmic Graph Theo? and Perfect Graphs. Academic Press, San Diego, Calif., 1980.
	9	~GUIBAS, m. J., AND SEDGEWICK, R. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundattons of Computer Sctence. IEEE, New York, 1978, pp. 8-21.
	10	Dan Halperin , Mark H. Overmars , Micha Sharir, Efficient motion planning for an L-shaped object, SIAM Journal on Computing, v.21 n.1, p.1-23, Feb. 1992 [doi>10.1137/0221001]
	11	J. A. La Poutré, New techniques for the union-find problem, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.54-63, January 22-24, 1990, San Francisco, California, United States
	12	J. A. La Poutré, Lower bounds for the union-find and the split-find problem on pointer machines, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.34-44, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100221]
	13	~MEHLHORN, K. Data Stntctures and Algorithms 1: Sorting and Searching. Springer-Verlag, Berlin, Germany, 1984.
	14	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	15	Kurt Mehlhorn , Stefan Näher , Helmut Alt, A lower bound on the complexity of the union-split-find problem, SIAM Journal on Computing, v.17 n.6, p.1093-1102, Dec. 1988 [doi>10.1137/0217070]
	16	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	17	~TARJAN, R.E. A class of algorithms which require nonlinear t~me to maintain disjoint sets. J. Comput. Sww. Scl. 18 (1979), ll0 127.
	18	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	19	Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]

CITED BY 4

	Adam L. Buchsbaum , Robert E. Tarjan, Confluently persistent deques via data structuaral bootstrapping, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.155-164, January 25-27, 1993, Austin, Texas, United States
	Inbok Lee , Kunsoo Park , Yanghee Choi , Sung Kwon Chung, A simple and scalable algorithm for the IP address lookup problem, Fundamenta Informaticae, v.56 n.1,2, p.181-190, July 2003
	Martin Raussen, On the classification of dipaths in geometric models for concurrency, Mathematical Structures in Computer Science, v.10 n.4, p.427-457, August 2000
	Joan Boyar , Lene M. Favrholdt , Kim S. Larsen, The relative worst-order ratio applied to paging, Journal of Computer and System Sciences, v.73 n.5, p.818-843, August, 2007