Robert Sedgewick: Algorithmen

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


24. Elementare geometrische Methoden



Ausblick

Aus den wenigen angeführten Beispielen sollte deutlich werden, daß man die Schwierigkeit der Lösung geometrischer Probleme mit Hilfe eines Computers leicht unterschätzen kann. Es gibt viele andere elementare geometrische Berechnungen, die wir überhaupt nicht behandelt haben. Zum Beispiel stellt ein Programm zur Berechnung der Fläche eines Polygons eine interessante Übung dar. Die betrachteten Probleme haben uns jedoch einige grundlegende Werkzeuge in die Hand gegeben, die in späteren Abschnitten für die Lösung der komplizierteren Probleme von Nutzen sein werden.

Einige der zu untersuchenden Algorithmen betreffen die Erzeugung geometrischer Strukturen aus einer gegebenen Menge von Punkten. Das einfache geschlossene Polygon ist ein elementares Beispiel hierfür. Wir werden Entscheidungen hinsichtlich geeigneter Darstellungen für solche Strukturen treffen, Algorithmen für ihre Erzeugung entwickeln und ihren Nutzen in speziellen Anwendungsfällen untersuchen müssen. In der Regel sind diese Überlegungen miteinander verflochten. Zum Beispiel hängt der in der Prozedur inside im vorliegenden Kapitel verwendete Algorithmus in entscheidendem Maße von der Darstellung des Polygons als geordneter Punktmenge ab (statt als ungeordneter Menge von Linien).

Viele der von uns zu betrachtenden Algorithmen erfordern geometrische Suche: Wir möchten wissen, welche Punkte aus einer gegebenen Menge nahe bei einem gegebenen Punkt liegen, welche Punkte in ein gegebenes Rechteck fallen oder welche Punkte den geringsten Abstand voneinander haben. Viele der für solche Suchprobleme geeigneten Algorithmen stehen in engem Zusammenhang mit den in den Kapiteln 14-17 untersuchten Suchalgorithmen. Die Parallelen werden sehr deutlich sein.

Wenige geometrische Algorithmen sind so eingehend untersucht worden, daß genaue Aussagen über ihre jeweiligen Leistungsmerkmale möglich sind. Wie wir bereits gesehen haben, kann die Laufzeit eines geometrischen Algorithmus von vielen Faktoren abhängen. Die Verteilung der Punkte selbst, die Reihenfolge, in der sie vorliegen, und die Frage, ob trigonometrische Funktionen benutzt werden, können alle einen beträchtlichen Einfluß auf die Laufzeit geometrischer Algorithmen haben. Wir haben jedoch, wie gewöhnlich in solchen Situationen, empirische Nachweise, aus denen sich die Eignung bestimmter Algorithmen für spezielle Anwendungen ergibt. Außerdem wurden viele der Algorithmen aus Komplexitätsuntersuchungen abgeleitet und mit dem Ziel einer guten Leistungsfähigkeit im ungünstigsten Fall entwickelt.


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