Please use this identifier to cite or link to this item: doi:10.22028/D291-26117
Title: Dynamic fractional cascading
Author(s): Mehlhorn, Kurt
Näher, Stefan
Language: English
Year of Publication: 1986
OPUS Source: Saarbrücken, 1986
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: 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).
Link to this record: urn:nbn:de:bsz:291-scidok-41580
Series name: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Series volume: 1986/06
Date of registration: 5-Sep-2011
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14_1986_06.pdf7,78 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.