DYNAMIC FRACTIONAL CASCADING

The problem of searching for a key in many ordered lists arises frequently in computational geometry. Chazelle and Guibas recently introduced fractional cascading as a general technique for solving this type of problem. In this paper we show that fractional cascading also supports insertions into and deletions from the lists efficiently. More specifically, we show that a search for a key in n lists takes time O(log N +n log log N) and an insertion or deletion takes time O(log log N). Here N is the total size of all lists. If only insertions or deletions have to be supported the O(log log N) factor reduces to O(1). As an application we show that queries, insertions, and deletions into segment trees or range trees can be supported in time O(log n log log n), when n is the number of segments (points). © 1990 Springer-Verlag New York Inc.