Dynamic fractional cascading. (English) Zbl 0693.68038

Let U be an ordered set and let \(G=(V,E)\) be an undirected graph. For each \(v\in V\) there is a set C(v)\(\subseteq U\), the catalogue of v, and for every edge \(e\in E\) there is a range \(R(e)=[7(e),r(e)]\), which is a closed interval in U. \(N=\sum_{v\in V}| C(v)|\) is the total size of the catalogues. The goal is to organize the catalogues in a data structure so that deletion, insertions and queries can be supported efficiently. Chazelle and Guibas introduced fractional cascading as a general data-structuring technique for approaching this kind of problems; however, they provided efficient \(O(n+\log N)\) algorithm for queries only under some restrictions on the graph G. The authors give general algorithms that support queries in time \(0(\log (N+| E|)+n \log \log (N+| E|))\) and deletions and insertions in O(log log(N\(+| E|))\). Detailed analysis and some applications are also given.
Reviewer: G.Slutzki


68P10 Searching and sorting
68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
68U99 Computing methodologies and applications
Full Text: DOI


[1] J. L. Bentley: Solutions to Klee’s Rectangle Problem, unpublished manuscript, Department of Computer Science, Carnegie-Mellon University, 1977.
[2] J. L. Bentley: Decomposable Searching Problems,Inform. Process. Lett. 8, 1979, 244–251. · Zbl 0404.68067
[3] N. Blum, K. Mehlhorn: On the Average Number of Rebalancing Operations in Weight-Balanced Trees,Theoret. Comput. Sci 11, 1980, 303–320. · Zbl 0435.68051
[4] B. Chazelle, L. Guibas: Fractional Cascading: I, A Data Structuring Technique; II, Applications,Algorithmica 1, 1986, 133–191. · Zbl 0639.68056
[5] J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan: Making Data Structures Persistent,J. Comput. System Sci, to appear. · Zbl 0667.68026
[6] H. Edelsbrunner, L. Guibas, I. Stolfi: Optimal Point Location in a Monotone Subdivision,SIAM J. Comput. 15, 1986, 317–340. · Zbl 0602.68102
[7] P. van Emde Boas, R. Kaas, E. Zijlstra: Design and Implementation of an Efficient Priority Queue,Math. Systems Theory 10, 1977, 99–127. · Zbl 0363.60104
[8] O. Fries, K. Mehlhorn, St. Näher: Dynamization of Geometric Data Structures,Proc. ACM Symposium on Computational Geometry, 1985, 168–176.
[9] H. N. Gabow, R. E. Tarjan: A Linear-Time Algorithm for a Special Case of Disjoint Set Union,J. Comput. System Sci 30, 1985, 209–221. · Zbl 0572.68058
[10] R. H. Güting: Fast Dynamic Intersection Searching in a Set of Isothetic Line Segments,Inform. Process. Lett. 21, 1985, 165–171. · Zbl 0577.68069
[11] S. Huddleston, K. Mehlhorn: A New Representation for Linear Lists,Acta Inform. 17, 1982, 157–184. · Zbl 0481.68061
[12] T. Imai, T. Asano: Dynamic Orthogonal Segment Intersection Search,J. Algorithms 8, 1987, 1–18. · Zbl 0642.68117
[13] W. Lipski: Finding a Manhattan Path and Related Problems,Networks 13, 1983, 399–409. · Zbl 0531.68018
[14] W. Lipski: AnO(n logn) Manhattan Path Algorithm,Inform. Process. Lett. 19, 1984, 99–102. · Zbl 0542.68052
[15] G. S. Luecker: A Data Structure for Orthogonal Range Queries,Proc. 19th FOCS, 1978, 28–34.
[16] K. Mehlhorn:Data Structures and Algorithms, Vol. 1, Springer-Verlag, Berlin, 1984. · Zbl 0556.68002
[17] Ibid..
[18] Ibid..
[19] K. Mehlhorn:Datenstrukturen und Algorithmen 1, Teubner, 1986.
[20] K. Mehlhorn, S. Näher, H. Alt: A Lower Bound on the Complexity of the Union-Split-Find Problem,Proc. 13th ICALP, 1987, 479–488.
[21] S. Näher: Dynamic Fractional Cascading oder die Verwaltung vieler linearer Listen, Dissertation, University des Saarlandes, Saarbrücken, 1987.
[22] F. P. Preparata, M. I. Shamos:Computational Geometry, An Introduction, Springer-Verlag, Berlin, 1985. · Zbl 0575.68059
[23] R. E. Tarjan: Amortized Computational Complexity,SIAM J. Algebraic Discrete Methods 6, 1985, 306–318. · Zbl 0599.68046
[24] A. K. Tsakalidis: Maintaining Order in a Generalized Linked List,Acta Inform. 21, 1984, 101–112. · Zbl 0527.68028
[25] V. K. Vaishnavi, D. Wood: Rectilinear Line Segment Intersection, Layered Segment Trees and Dynamization,J. Algorithms,3, 1982, 160–176. · Zbl 0481.68062
[26] D. E. Willard: New Data Structures for Orthogonal Range Queries, Technical Report, Harvard University, 1978. · Zbl 0564.68071
[27] D. E. Willard: New Data Structures for Orthogonal Queries,SIAM J. Comput., 1985, 232–253. · Zbl 0564.68071
[28] D. E. Willard, G. S. Luecker: Adding Range Restriction Capability to Dynamic Data Structures,J. Assoc. Comput. Mach. 32, 1985, 597–617. · Zbl 0629.68097
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.