Linear space data structures for two types of range search (Q578916)

Für den zwei- und den dreidimensionalen euklidischen Raum werden Aufgaben der ``Bereichssuche'' betrachtet: Seien eine Menge von n Punkten im Raum und eine Menge von Teilbereichen des Raumes gegeben (im \(E^ 2\) sind dies in dieser Arbeit alle Dreiecke, deren Seiten parallel zu drei gegebenen Richtungen sind - im \(E^ 3\) sind es die unendlich großen Oktanten, die sich von einem beliebigen Punkt aus parallel zu den Achsen jeweils ins negativ Unendliche erstrecken). Gefragt wird nach der Komplexität der Algorithmen, welche alle Punkte der gegebenen Mengen ermitteln, die in einem der Teilbereiche liegen. Als neues Resultat können die Autoren angeben: Der benötigte Speicherplatz hat lineare Komplexität O(n) und die Bearbeitungszeit für eine Anfrage im \(E^ 2\) bzw. im \(E^ 3\) verhält sich wie \(O(k+\log n)\) resp. \(O(k+\log^ 2n)\), wobei k die Anzahl der gefundenen Punkte ist. Erreichbar wurde dies durch einen aufwendigeren Vorprozeß, welcher die gegebenen n Punkte in einer baumartigen Datenstruktur ``vorsortiert'' und der sich bei vielen Anfragen gewissermaßen amortisiert.