TY  - RPRT
T1  - Dynamic fractional cascading
T3  - Saarbrücken, 1986
A1  - Mehlhorn,Kurt
A1  - Näher,Stefan
Y1  - 2011/09/05
N2  - 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 the present 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+nloglogN) and an insertion or deletion takes time O(loglogN). Here N is the total size of all lists. If only insertions or deletions have to be supported the O(loglogN) 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 t ime O(lognloglogn), when n is the number of segments (points).

CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2011/4158
ER  -