Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26117
Titel: Dynamic fractional cascading
Verfasser: Mehlhorn, Kurt
Näher, Stefan
Sprache: Englisch
Erscheinungsjahr: 1986
Quelle: Saarbrücken, 1986
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: 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 zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-41580
hdl:20.500.11880/26173
http://dx.doi.org/10.22028/D291-26117
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Band: 1986/06
SciDok-Publikation: 5-Sep-2011
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1986_06.pdf7,78 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.