Das Hauptziel der Forschung im Bereich der kombinatorischen computergestützten Geometrie ist die Entwicklung effizienter Algorithmen und Datenstrukturen zur Lösung von Problemen, die in Form grundlegender geometrischer Objekte formuliert sind: Punkte, Liniensegmente, Polygone, Polyeder usw.
Einige dieser Probleme scheinen so einfach zu sein, dass sie bis zum Aufkommen der Computer überhaupt nicht als Probleme betrachtet wurden. Betrachten wir zum Beispiel das Problem des engsten Paares:
- Gegeben n Punkte in der Ebene, finde die zwei mit dem kleinsten Abstand voneinander.
Man könnte die Abstände zwischen allen Punktpaaren berechnen, von denen es n(n-1)/2 gibt, und dann das Paar mit dem kleinsten Abstand auswählen. Dieser Brute-Force-Algorithmus benötigt O(n2) Zeit, d.h. seine Ausführungszeit ist proportional zum Quadrat der Anzahl der Punkte. Ein klassisches Ergebnis in der numerischen Geometrie war die Formulierung eines Algorithmus, der O(n log n) benötigt. Randomisierte Algorithmen, die O(n) erwartete Zeit benötigen, sowie ein deterministischer Algorithmus, der O(n log log n) Zeit benötigt, wurden ebenfalls entdeckt.
ProblemklassenBearbeiten
Die Kernprobleme in der rechnergestützten Geometrie können auf verschiedene Weise nach unterschiedlichen Kriterien klassifiziert werden. Die folgenden allgemeinen Klassen können unterschieden werden.
Statische ProblemeBearbeiten
Bei den Problemen dieser Kategorie ist eine Eingabe gegeben und die entsprechende Ausgabe muss konstruiert oder gefunden werden. Einige grundlegende Probleme dieses Typs sind:
- Konvexe Hülle: Finden Sie bei einer gegebenen Menge von Punkten das kleinste konvexe Polyeder/Polygon, das alle Punkte enthält.
- Schnittpunkte von Liniensegmenten: Finde die Schnittpunkte zwischen einer gegebenen Menge von Liniensegmenten.
- Delaunay-Triangulation
- Voronoi-Diagramm: Bei einer Menge von Punkten den Raum danach aufteilen, welche Punkte den gegebenen Punkten am nächsten sind.
- Lineare Programmierung
- Nächstes Punktpaar: Finde bei einer Menge von Punkten die beiden mit dem geringsten Abstand zueinander.
- Weitestes Punktpaar
- Größter leerer Kreis: Finde bei einer Menge von Punkten den größten Kreis, dessen Mittelpunkt innerhalb ihrer konvexen Hülle liegt und keinen der Punkte einschließt.
- Euklidischer kürzester Weg: Verbinde zwei Punkte in einem euklidischen Raum (mit polyedrischen Hindernissen) durch einen kürzesten Weg.
- Polygon-Triangulation: Partitioniere das Innere eines Polygons in Dreiecke
- Netzgenerierung
- Boolesche Operationen auf Polygonen
Die Rechenkomplexität für diese Klasse von Problemen wird durch die Zeit und den Platz (Computerspeicher) geschätzt, die zur Lösung einer gegebenen Probleminstanz erforderlich sind.
Geometrische AbfrageproblemeBearbeiten
Bei geometrischen Abfrageproblemen, die allgemein als geometrische Suchprobleme bekannt sind, besteht die Eingabe aus zwei Teilen: dem Suchraumteil und dem Abfrageteil, der sich über die Probleminstanzen hinweg verändert. Der Suchraum muss typischerweise so vorverarbeitet werden, dass mehrere Anfragen effizient beantwortet werden können.
Einige grundlegende geometrische Suchprobleme sind:
- Bereichssuche: Eine Menge von Punkten muss vorverarbeitet werden, um die Anzahl der Punkte innerhalb eines Abfragebereichs effizient zu zählen.
- Punktortung: Ausgehend von einer Partitionierung des Raums in Zellen wird eine Datenstruktur erstellt, die effizient angibt, in welcher Zelle sich ein Abfragepunkt befindet.
- Nächster Nachbar: Vorverarbeitung einer Menge von Punkten, um effizient herauszufinden, welcher Punkt am nächsten zu einem Abfragepunkt liegt.
- Raytracing: Bei einer Menge von Objekten im Raum eine Datenstruktur erzeugen, die effizient angibt, welches Objekt ein Abfragestrahl zuerst schneidet.
Wenn der Suchraum fest ist, wird die Rechenkomplexität für diese Klasse von Problemen gewöhnlich geschätzt durch:
- die Zeit und den Raum, die erforderlich sind, um die Datenstruktur zu konstruieren, in der gesucht werden soll
- die Zeit (und manchmal einen zusätzlichen Raum), um Abfragen zu beantworten.
Für den Fall, dass der Suchraum variieren darf, siehe „Dynamische Probleme“.
Dynamische ProblemeBearbeiten
Eine weitere wichtige Klasse sind die dynamischen Probleme, bei denen das Ziel darin besteht, einen effizienten Algorithmus zu finden, der nach jeder inkrementellen Änderung der Eingabedaten (Hinzufügung oder Löschung von geometrischen Elementen) wiederholt eine Lösung findet. Algorithmen für diese Art von Problemen beinhalten typischerweise dynamische Datenstrukturen. Jedes rechnerische geometrische Problem kann in ein dynamisches Problem umgewandelt werden, allerdings auf Kosten einer höheren Verarbeitungszeit. So kann beispielsweise das Problem der Bereichssuche in das Problem der dynamischen Bereichssuche umgewandelt werden, indem das Hinzufügen und/oder Löschen von Punkten vorgesehen wird. Das dynamische Problem der konvexen Hülle besteht darin, die konvexe Hülle zu verfolgen, z. B. für die sich dynamisch ändernde Menge von Punkten, d. h., während die Eingabepunkte eingefügt oder gelöscht werden.
Die Berechnungskomplexität für diese Klasse von Problemen wird geschätzt durch:
- die Zeit und den Raum, die erforderlich sind, um die Datenstruktur zu konstruieren, in der gesucht werden soll
- die Zeit und den Raum, um die gesuchte Datenstruktur nach einer inkrementellen Änderung im Suchraum zu modifizieren
- die Zeit (und manchmal einen zusätzlichen Raum), um eine Anfrage zu beantworten.
VariationenBearbeiten
Einige Probleme können je nach Kontext als zu einer der beiden Kategorien gehörig betrachtet werden. Betrachten wir zum Beispiel das folgende Problem:
- Punkt in Polygon: Entscheide, ob ein Punkt innerhalb oder außerhalb eines gegebenen Polygons liegt.
In vielen Anwendungen wird dieses Problem als ein einmaliges Problem behandelt, d.h. es gehört zur ersten Klasse. Zum Beispiel besteht in vielen Anwendungen der Computergrafik ein häufiges Problem darin, herauszufinden, welcher Bereich auf dem Bildschirm von einem Zeiger angeklickt wird. In einigen Anwendungen ist das betreffende Polygon jedoch unveränderlich, während der Punkt eine Abfrage darstellt. Beispielsweise kann das Eingabepolygon die Grenze eines Landes darstellen und der Punkt die Position eines Flugzeugs, und das Problem besteht darin, festzustellen, ob das Flugzeug die Grenze verletzt hat. Schließlich werden in dem bereits erwähnten Beispiel der Computergrafik in CAD-Anwendungen die sich ändernden Eingabedaten oft in dynamischen Datenstrukturen gespeichert, was zur Beschleunigung der Punkt-in-Polygon-Abfragen ausgenutzt werden kann.
In einigen Zusammenhängen von Abfrageproblemen gibt es vernünftige Erwartungen an die Reihenfolge der Abfragen, die entweder für effiziente Datenstrukturen oder für engere Schätzungen der Rechenkomplexität ausgenutzt werden können. Zum Beispiel ist es in manchen Fällen wichtig, den ungünstigsten Fall der Gesamtzeit für die gesamte Folge von N Abfragen zu kennen und nicht nur für eine einzelne Abfrage. Siehe auch „amortisierte Analyse“.