Dynamic fractional cascading
type: Item
instance of: scholarly article
title: Dynamic fractional cascading
zbMATH Open document ID: 0693.68038
DOI: 10.1007/BF01840386
author: K. Mehlhorn
author: S. Näher
published in: Algorithmica
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U99
zbMATH DE Number: 4135411
zbMATH Keywords: computational geometry
zbMATH Keywords: linear lists
zbMATH Keywords: dynamic data structures
zbMATH Keywords: amortized complexity
zbMATH Keywords: fractional cascading
reviewed by: Giora Slutzki
MaRDI profile type: Publication
Wikidata QID: Q30048731
cites work: Decomposable searching problems
cites work: On the average number of rebalancing operations in weight-balanced trees
cites work: Fractional cascading. I: A data structuring technique
cites work: Making data structures persistent
cites work: Optimal Point Location in a Monotone Subdivision
cites work: Design and implementation of an efficient priority queue
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: Fast dynamic intersection searching in a set of isothetic line segments
cites work: A new data structure for representing sorted lists
cites work: Dynamic orthogonal segment intersection search
cites work: Finding a manhattan path and related problems
cites work: An O(n log n) Manhattan path algorithm
cites work: Q3219751
cites work: Q3219752
cites work: Q3219753
cites work: Q3747740
cites work: Q3992847
cites work: Amortized Computational Complexity
cites work: Maintaining order in a generalized linked list
cites work: Rectilinear line segment intersection, layered segment trees, and dynamization
cites work: New Data Structures for Orthogonal Range Queries
cites work: Adding range restriction capability to dynamic data structures
full work available at URL: https://doi.org/10.1007/bf01840386
OpenAlex ID: W2061750047
DBLP publication ID: journals/algorithmica/MehlhornN90
description: scientific article; zbMATH DE number 4135411