×

zbMATH — the first resource for mathematics

Fractional cascading. I: A data structuring technique. (English) Zbl 0639.68056
Summary: In computational geometry many search problems and range queries can be solved by performing an iterative search for the same key in separate ordered lists. In this paper we show that, if these ordered lists can be put in a one-to-one correspondence with the nodes of a graph of degree d so that the iterative search always proceeds along edges of that graph, then we can do much better than the obvious sequence of binary searches. Without expanding the storage by more than a constant factor, we can build a data-structure, called a fractional cascading structure, in which all original searches after the first can be carried out at only log d extra cost per search. Several results related to the dynamization of this structure are also presented. A companion paper (see the following review) gives numerous applications of this technique to geometric problems.

MSC:
68P10 Searching and sorting
68P05 Data structures
68P20 Information storage and retrieval of data
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. L. Bentley and J. B. Saxe.Decomposable searching problems I: static to dynamic transformations. J. Algorithms, 1 (1980), 301–358. · Zbl 0461.68065
[2] P. van Emde Boas, B. Kaas and E. Zijlstra.Design and implementation of an efficient priority queue. Math. Syst. Theory,10 (1977), 99–127. · Zbl 0363.60104
[3] B. Chazelle.Filtering search: A new approach to query-answering. Proc. 24th Ann. Symp. Found. Comp. Sci. (1983), pp. 122–132. To appear in SIAM J. Comput. (1986).
[4] B. Chazelle and L. J. Guibas.Fractional cascading II: applications. To appear in Algorithmica (1986). · Zbl 0639.68057
[5] R. Cole.Searching and storing similar lists. Tech. Report No. 88, Courant Inst., New York University, New York, Oct. 1983. To apper in J. Algorithms. · Zbl 0605.68053
[6] O. Fries, K. Mehlhorn, and St. Näher.Dynamization of geometric data structures. Proc. 1st ACM Computational Geometry Symposium, 1985, pp. 168–176.
[7] H. Edelsbrunner, L. J. Guibas, and J. Stolfi.Optimal point location in a monotone subdivision. To appear in SIAM J. Comput. Also DEC/SRC Research Report No. 2, 1984. · Zbl 0602.68102
[8] H. Imai and T. Asano.Dynamic segment intersection search with applications, Proc. of 25th FOCS Sumposium, 1984, pp. 393–402.
[9] H. N. Gabow and R. E. Tarjan.A linear-time algorithm for a special case of disjoint set union. Proc. of 24th FOCS Symposium, 1983, pp. 246–251.
[10] M. H. Overmars.The design of dynamic data structures. PhD Thesis, University of Utrecht, The Netherlands, 1983. · Zbl 0545.68009
[11] R. E. Tarjan.Amortized computational complexity. SIAM J. Alg. Disc. Meth.,6 (2) (April 1985), 306–318. · Zbl 0599.68046
[12] V. K. Vaishani and D. Wood.Rectilinear line segment intersection, layered segment trees, and dynamization. J. Algorithms,3 (1982), 160–176. · Zbl 0481.68062
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.