ISSN:
1436-5057
Keywords:
decomposable searching problem
;
dynamization
;
merging
;
quad-trees
;
k-d trees
;
halfspaces
;
maximal elements
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Wir definieren zwei Klassen zerlegbarer Suchprobleme und untersuchen, wie man diese Probleme effizient dynamisch lösen könnte. Für die erste Klasse (DD) zeigen wir, daß man sowohl das Einfügen als auch das Streichen von einzelnen Elementen im Zeitmittel effizient durchführen kann. Für die zweite Klasse (MD) zeigen wir zudem, daß man mit der Benützung einer schnellen Mischungsprozedur die Effizienz noch um ein wenig verbessern kann. Alss Anwendungen zeigen wir z. B. die effiziente Dynamisierung von Quadbäumen und vom gemeinsamen Durchschnitt endlich vieler Halbebenen in der Ebene.
Notes:
Abstract We define two classes of decomposable searching problems and consider ways of efficiently dynamizing them. For the first class, DD, we show that both insertions and deletions can be processed efficiently. For the second class, MD, we exploit a merge technique to obtain better insertion times. We also give a number of examples of problems to which the methods apply, including the dynamic maintenance of quadtrees and of the common intersection of finitely many halfspaces in the plane.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02241781
