SciDok

Eingang zum Volltext in SciDok

Lizenz

Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-41580
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4158/


Dynamic fractional cascading

Mehlhorn, Kurt ; Näher, Stefan

Quelle: (1986) Saarbrücken, 1986
pdf-Format:
Dokument 1.pdf (7.784 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Institut: Fachrichtung 6.2 - Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Bandnummer: 1986/06
Sprache: Englisch
Erstellungsjahr: 1986
Publikationsdatum: 05.09.2011
Kurzfassung auf Englisch: 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).
Lizenz: Standard-Veröffentlichungsvertrag

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English