Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


28. Probleme des nächsten Punktes



Geometrische Probleme, bei denen Punkte in der Ebene eine Rolle spielen, erfordern gewöhnlich eine implizite oder explizite Verarbeitung von Abständen zwischen den Punkten. Ein sehr natürliches Problem, das in vielen Anwendungen auftritt, ist zum Beispiel das Problem d
es nächsten Nachbarn: Finde denjenigen Punkt aus einer Menge von gegebenen Punkten, der zu einem gegebenen neuen Punkt am nächsten liegt. Dazu scheint es erforderlich zu sein, den Abstand des gegebenen Punkts zu jedem Punkt in der Menge zu prüfen, doch es sind viel bessere Lösungen möglich. Im vorliegenden Abschnitt betrachten wir einige weitere Abstandsprobleme, den Prototyp eines Algorithmus und eine grundlegende geometrische Struktur, die Voronoi-Diagramm genannt wird und für eine Vielzahl solcher Probleme in der Ebene effizient verwendet werden kann. Unsere Vorgehensweise wird darin bestehen, daß wir ein allgemeines Verfahren zur Lösung von Problemen des nächsten Punktes über die gründliche Betrachtung eines Prototyps einer Implementation für ein einfaches Problem beschreiben.

Einige der Fragen, die wir in diesem Kapitel betrachten, sind den Problemen der Bereichssuche aus Kapitel 26 ähnlich, und das Gitterverfahren und das 2D-Baum-Verfahren, die dort entwickelt wurden, sind für die Lösung des Problems des nächsten Nachbarn und anderer Aufgaben geeignet. Der grundlegende Nachteil dieser Methoden besteht jedoch darin, daß sie von Zufälligkeit in der Punktmenge ausgehen: Sie zeigen ein schlechtes Verhalten im ungünstigsten Fall. Unser Ziel besteht in diesem Kapitel darin, einen anderen allgemeinen Ansatz zu untersuchen, der für viele Probleme unabhängig von den Eingabedaten eine gute Leistungsfähigkeit garantiert. Einige der Verfahren sind zu kompliziert, um eine vollständige Implementation zu betrachten, und sie beinhalten so viel Ballast, daß die einfachen Verfahren besser geeignet sind, wenn die Punktmenge nicht zu groß ist oder wenn sie genügend gut verteilt ist. Trotzdem wird die Untersuchung von Verfahren mit guter Leistungsfähigkeit im ungünstigsten Fall einige grundlegende Eigenschaften von Punktmengen sichtbar machen, deren Verständnis auch dann von Nutzen ist, wenn einfachere Methoden in speziellen Situationen geeigneter sind.

Der allgemeine Ansatz, den wir betrachten wollen, liefert noch ein weiteres Beispiel für die Nützlichkeit von doppelt rekursiven Prozeduren für die Verflechtung der Verarbeitungsprozesse längs der beiden Koordinatenrichtungen. Die beiden Verfahren dieses Typs, die wir zuvor kennengelernt haben (kD-Bäume und Schnitt von Linien), beruhten auf binären Suchbäumen; die jetzt betrachtete Methode ist ein Verfahren vom Typ »Kombiniere und Herrsche«, das auf Mergesort beruht.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]