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 hdl:20.500.11880/26173 http://dx.doi.org/10.22028/D291-26117 |
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 | Size | Format | |
---|---|---|---|---|
fb14_1986_06.pdf | 7,78 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.