Algorithmen in einer Kurzfassung, 2.

Kapitel 10. Räumliche Baum-Strukturen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Die Algorithmen in diesem Kapitel befassen sich in erster Linie mit der Modellierung zweidimensionaler Strukturen über der kartesischen Ebene, um leistungsfähige Suchabfragen durchzuführen, die über die einfache Zugehörigkeit, wie sie in Kapitel 5 behandelt wird, hinausgehen. Diese Algorithmen umfassen:

Nächster Nachbar

Bestimme bei einer Menge von zweidimensionalen Punkten P, welcher Punkt am nächsten zu einem Zielpunkt x liegt. Diese Aufgabe kann in O(log n) gelöst werden, anstatt einer O(n) Brute-Force-Lösung.

Bereichsabfragen

Bestimme bei einer Menge von zweidimensionalen Punkten P, welche Punkte in einem bestimmten rechteckigen Bereich enthalten sind. Diese Aufgabe kann in O(n0^,5 + r) gelöst werden, wobei r die Anzahl der gemeldeten Punkte ist, anstatt einer O(n)-Lösung mit roher Gewalt.

Abfragen von Schnittpunkten

Bestimme aus einer Menge von zweidimensionalen Rechtecken R, welche Rechtecke eine rechteckige Zielregion schneiden. Diese Aufgabe kann in O(log n) anstelle einer O(n) Brute-Force-Lösung gelöst werden.

Kollisionserkennung

Bestimme bei einer Menge von zweidimensionalen Punkten P die Schnittpunkte zwischen Quadraten der Seite s, die auf diesen Punkten liegen. Diese Aufgabe kann in O(n log n) anstelle einer O(ⁿ²) Brute-Force-Lösung gelöst werden.

Die Strukturen und Algorithmen lassen sich ...