Was ist Algorithmische Geometrie?

Bereits im Altertum haben sich Wissenschaftler wie Pythagoras und Euklid mit geometrischen Problemen beschäftigt. Ihr Interesse galt der Entdeckung geometrischer Sachverhalte und deren Beweis. Sie operierten ausschließlich mit geometrischen Figuren (Punkten, Geraden, Kreisen etc.). Erst die Einführung von Koordinaten durch Descartes machte es möglich, geometrische Objekte durch Zahlen zu beschreiben.

Die Algorithmische Geometrie (Engl.: Computational Geometry) beschäftigt sich mit

• der Entwicklung von effizienten und praktikablen Algorithmen zur Lösung geometrischer Probleme,

• der Bestimmung der algorithmischen Komplexität geometrischer Probleme.

Die untersuchten Probleme haben (zumindest theoretisch betrachtet) durchaus reale Anwendungshintergründe. Bei der Bahnplanung für Roboter geht es zum Beispiel darum, eine Bewegung von einer Anfangskonfiguration in eine Endkonfiguration zu planen, die Kollisionen mit der Umgebung vermeidet und außerdem möglichst effizient ist. Wer je eine Leiter durch verwinkelte Korridore getragen hat, kann sich ein Bild von der Schwierigkeit dieser Aufgabe machen. Sie wächst noch, wenn der Roboter seine Umgebung noch gar nicht kennt, sondern sie während der Ausführung erkunden muß.

Beim computer aided geometric design (CAGD) kommt es unter anderem darauf an, Durchschnitt und Vereinigung von dreidimensionalen Körpern schnell zu berechnen. Oder es sollen interpolierende Flächen durch vorgegebene Stützpunkte konstruiert werden.

Bei der Arbeit mit geographischen Daten, die in der Regel in Datenbanken gespeichert sind, müssen immer wieder Anfragen beantwortet werden, die sich auf Kombinationen von geometrischen Eigenschaften und Standardmerkmalen beziehen. So möchte man zum Beispiel wissen, welche Städte im Ruhrgebiet vom nächstgelegenen Erholungsgebiet mehr als k Kilometer weit entfernt sind.

Neben diesen großen Anwendungsbereichen gibt es zahlreiche Einzelanwendungen von Methoden der Algorithmischen Geometrie, zum Beispiel beim Fräsen metallener Werkstücke. Und ein großer amerikanischer Jeans-Hersteller verwendet geometrische Verfahren, um die zuzuschneidenden Einzelteile so auf der Stoffbahn zu plazieren, daß möglichst wenig Abfall entsteht.

Oft tritt der geometrische Kern komplizierter Anwendungsprobleme viel deutlicher zutage, wenn man von nebensächlichen Bedingungen abstrahiert. Nehmen wir zum Beispiel für eine GIS-Applikation an, daß für jedes Haus in einer dünn besiedelten Gegend das nächstgelegene Nachbarhaus ermittelt werden soll. Da die Abstände zwischen den Häusern relativ groß sind, können wir sie uns einfach als Punkte in der Ebene vorstellen. Damit hat unsere Aufgabe folgende Form: Gegeben sind n Punkte in der Ebene. Zu jedem Punkt soll sein nächster Nachbar bestimmt werden. Auf Englisch heißt dieses Problem all nearest neighbors. Das folgende Bild zeigt ein Beispiel mit 11 Punkten; die Pfeile weisen jeweils zum nächsten Nachbarn.

Elf Punkte und ihre nächsten Nachbarn.

Eine mögliche Lösung liegt auf der Hand: Man könnte nacheinander jeden der n Punkte hernehmen und die Abstände zu allen übrigen n-1 Punkten bestimmen; der Punkt mit dem kleinsten Abstand ist dann der gesuchte nächste Nachbar des gerade betrachteten Punkts. Bei diesem Vorgehen werden mindestens n(n-1)/2 Berechnungen durchgeführt, weil jedes Punktepaar einmal betrachtet wird. Für n=1000000 wäre auch ein schneller Computer einige Zeit beschäftigt!

Für die Algorithmische Geometrie stellt sich hier die Frage, ob das Problem der nächsten Nachbarn sich nicht auch effizienter lösen läßt. Unter Effizienz verstehen wir den sparsamen Umgang mit den Ressourcen Rechenzeit und Speicherplatz (in unserem Beispiel liegt das Problem zunächst nur in der Rechenzeit). Im Unterschied zum Vorgehen rein theoretischer Wissenschaften können wir uns aber nicht damit begnügen, die bloße Existenz eines effizienten Lösungsverfahrens nachzuweisen. Wir wollen vielmehr unsere Algorithmen konkret angeben und im Prinzip auch implementieren können, denn nur so können wir zur Lösung realer Probleme beitragen.

Beim Problem all nearest neighbors läßt sich der Zeitaufwand verringern, indem man eine strukturelle Eigenschaft des Problems ausnutzt, die das naive Verfahren ganz übersieht: Zwei einander nahe Punkte haben auch einander ,, ziemlich nahe`` nächste Nachbarn. Unter Ausnutzung dieses Umstands kann man zeigen, daß man mit O(n log n) vielen Rechenschritten auskommen kann. (Eine Lösung in O(n log n) ist dann mittels der Theorie der Voronoi-Diagramme möglich.) Damit wird für 1000000 Punkte ein interaktives Arbeiten wieder möglich!

Natürlich stellt sich die Frage, ob man die Effizienz der Lösung noch weiter verbessern kann, etwa zu einer Anzahl von Rechenoperationen, die linear in n ist. Man kann ebenfalls zeigen, daß das nicht möglich ist: Kein Verfahren zur Lösung des Problems der nächsten Nachbarn kann mit weniger als größenordnungsmäßig n log n vielen Schritten auskommen. Diese untere Schranke zeigt, daß unsere O(n log n)-Algorithmen optimal bezüglich der Rechenzeit sind (im Hinblick auf den Speicherplatz sind sie es übrigens auch).

Durch beides zusammen -- die Angabe einer unteren Schranke und die Konstruktion eines Algorithmus, der diese Schranke nicht überschreitet -- ist die algorithmische Komplexität eines Problems festgelegt. Auch hierhin besteht eine Aufgabe der Algorithmischen Geometrie, die aber mitunter recht schwierig ist. Für zahlreiche wichtige Probleme ist die genaue Komplexität noch nicht bekannt. (Noch schwieriger ist im Allgemeinen die Angabe der durchschnittlichen Komplexität.)

Das Gebiet der Algorithmischen Geometrie ist noch recht jung. Seine Entwicklung begann mit der Arbeit von Shamos und Hoey im Jahre 1975 und verlief seitdem recht stürmisch: in einer elektronischen Bibliographie waren im Ende der 90er Jahre bereits rund 13000 einschlägige Arbeiten verzeichnet. Inzwischen haben sich einige algorithmische Techniken, sogenannte Paradigmen, als besonders wichtig herausgestellt, weil man mit ihrer Hilfe nicht nur ein einzelnes Problem, sondern eine Vielzahl von Problemen mit ähnlicher Grundstruktur lösen kann. Ihr prominentester Vertreter ist wohl das Sweep-Verfahren.

(Modifikation eines Auszugs aus dem Kurs "Algorithmische Geometrie" der FernUniversität Hagen; ursprünglicher Autor: Rolf Klein; Original unter http://pine.fernuni-hagen.de/GI/wasist/wasist.html zugänglich.)

file last modified: Tuesday, 12-Jul-2011 13:55:14 CEST Copyright © 2012 Martin Held. All rights reserved.