ISSN:
1436-5057
Schlagwort(e):
decomposable searching problem
;
dynamization
;
merging
;
quad-trees
;
k-d trees
;
halfspaces
;
maximal elements
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
Beschreibung / Inhaltsverzeichnis:
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.
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF02241781
