Computergeometrie

Für das Journal siehe Computergeometrie (Journal).

Computergeometrie ist ein Zweig von Informatik sich der Untersuchung von Algorithmen gewidmet, die in Bezug auf angegeben werden können Geometrie. Einige rein geometrische Probleme entstehen aus der Untersuchung des rechnerischen Geometrischen Algorithmenund solche Probleme werden auch als Teil der Computergeometrie angesehen. Während die moderne Computergeometrie eine jüngste Entwicklung ist, ist sie eines der ältesten Computerfelder mit einer Geschichte, die bis zur Antike zurückreicht.

Rechenkomplexität ist von zentraler Bedeutung für die Computergeometrie mit großer praktischer Bedeutung, wenn Algorithmen für sehr große Datensätze mit Zehn- oder Hunderten von Millionen Punkten verwendet werden. Für solche Sätze der Unterschied zwischen o ((n2) und o ((n Protokoll n) kann der Unterschied zwischen Tagen und Sekunden der Berechnung sein.

Der Hauptantrieb für die Entwicklung der Computergeometrie als Disziplin war der Fortschritt in Computergrafik und computergestütztes Design und Fertigung (CAD/NOCKEN), aber viele Probleme in der Computergeometrie sind klassischer Natur und können von kommen Mathematische Visualisierung.

Andere wichtige Anwendungen der Computergeometrie umfassen Robotik (Bewegungsplanung und Sichtbarkeitsprobleme), Geografisches Informationssystem (GIS) (geometrischer Standort und Suche, Routenplanung), Integrierter Schaltkreis Design (IC -Geometrie -Design und -überprüfung), computergestütztes Ingenieurwesen (CAE) (Maschengeneration) und Computer Vision (3D -Rekonstruktion).

Die Hauptzweige der Computergeometrie sind:

  • Kombinatorische Computergeometrie, auch genannt Algorithmische Geometrie, was sich mit geometrischen Objekten befasst diskret Entitäten. Ein über Erdungsbuch in diesem Thema von Preparata und Shamos datiert die erste Verwendung des Begriffs "Computergeometrie" in diesem Sinne bis 1975.[1]
  • Numerische Computergeometrie, auch genannt Maschinengeometrie, Computergestütztes geometrisches Design (CAGD) oder Geometrische Modellierung, das sich hauptsächlich mit der Darstellung realer Objekte in Formularen befasst, die für Computerberechnungen in CAD/CAM-Systemen geeignet sind. Dieser Zweig kann als Weiterentwicklung von gesehen werden Beschreibende Geometrie und wird oft als Zweig von Computergrafiken oder CAD angesehen. Der Begriff "Computergeometrie" in dieser Bedeutung wird seit 1971 verwendet.[2]

Obwohl die meisten Algorithmen der Computergeometrie für elektronische Computer entwickelt (und werden entwickelt), wurden einige Algorithmen für unkonventionelle Computer entwickelt (z. B. optische Computer [3]))

Kombinatorische Computergeometrie

Das Hauptziel der Forschung in der kombinatorischen Computergeometrie ist die Entwicklung effizienter Algorithmen und Datenstrukturen Für die Lösung von Problemen, die in Bezug auf grundlegende geometrische Objekte angegeben sind: Punkte, Liniensegmente, Polygone, Polyeder, etc.

Einige dieser Probleme scheinen so einfach zu sein, dass sie bis zum Aufkommen überhaupt nicht als Probleme angesehen wurden Computers. Betrachten Sie zum Beispiel die Das engste Paarproblem:

  • Gegeben n Punkte im Flugzeug finden Sie die beiden mit dem kleinsten Abstand voneinander.

Man könnte die Entfernungen zwischen allen Punktpaaren berechnen, von denen es gibt n (n-1)/2Wählen Sie dann das Paar mit der kleinsten Entfernung. Dies rohe Gewalt Algorithmus nimmt O(n2) Zeit; d.h. seine Ausführungszeit ist proportional zum Quadrat der Anzahl der Punkte. Ein klassisches Ergebnis bei der Computergeometrie war die Formulierung eines Algorithmus, der O (O.n Protokoll n). Randomisierte Algorithmen das dauert o (n) erwartete Zeit,[4] sowie ein deterministischer Algorithmus, der O (O.n Protokollprotokoll n) Zeit,[5] wurden auch entdeckt.

Problemklassen

Die Kernprobleme in der Computergeometrie können nach verschiedenen Kriterien auf unterschiedliche Weise eingestuft werden. Die folgenden allgemeinen Klassen können unterschieden werden.

Statische Probleme

In den Problemen dieser Kategorie wird einige Eingaben angegeben und die entsprechende Ausgabe muss konstruiert oder gefunden werden. Einige grundlegende Probleme dieser Art sind:

Die rechnerische Komplexität für diese Problemklasse wird nach Zeit und Raum (Computerspeicher) geschätzt, die zur Lösung einer bestimmten Probleminstanz erforderlich sind.

Geometrische Abfrageprobleme

Bei geometrischen Abfragenproblemen, die allgemein als geometrische Suchprobleme bezeichnet werden, besteht der Eingang aus zwei Teilen: die Suchraum Teil und die Anfrage Teil, der sich über die Probleminstanzen variiert. Der Suchraum muss normalerweise sein vorverarbeitetAuf eine Weise, dass mehrere Abfragen effizient beantwortet werden können.

Einige grundlegende geometrische Abfrageprobleme sind:

  • Bereichsuche: Vorbereitet eine Reihe von Punkten, um die Anzahl der Punkte in einem Abfragebereich effizient zu zählen.
  • Punktstandort: Bei einer Aufteilung des Raums in Zellen erzeugen Sie eine Datenstruktur, die effizient angibt, in welcher Zelle ein Abfragepunkt liegt.
  • Unmittelbarer Nachbar: Vorbereitet eine Reihe von Punkten, um effizient zu ermitteln, welcher Punkt einem Abfragepunkt am nächsten ist.
  • Strahlenverfolgung: Erstellen Sie bei einer Reihe von Objekten im Raum eine Datenstruktur, die effizient angibt, welches Objekt ein Abfragestrahl zuerst überschneidet.

Wenn der Suchraum festgelegt ist, wird die rechnerische Komplexität für diese Problemklasse normalerweise geschätzt:

  • Die Zeit und der Raum, der erforderlich ist, um die Datenstruktur zu konstruieren, die in der Suche nachgefragt werden muss
  • Die Zeit (und manchmal auch ein zusätzlicher Raum), um Fragen zu beantworten.

Für den Fall, in dem der Suchraum variieren darf, siehe "Dynamische Probleme".

Dynamische Probleme

Eine weitere große Klasse ist die Dynamische Probleme, in dem das Ziel darin besteht, einen effizienten Algorithmus zum Wiederholen einer Lösung nach jeder inkrementellen Modifikation der Eingabedaten (Zugabe oder Löschung Eingangsgeometrische Elemente) zu finden. Algorithmen für Probleme dieses Typs beinhalten normalerweise Dynamische Datenstrukturen. Jedes der geometrischen Rechenprobleme kann auf Kosten einer höheren Verarbeitungszeit in eine dynamische Umgebung umgewandelt werden. Zum Beispiel die Bereichsuche Das Problem kann in das Problem der Dynamikbereichsuche umgewandelt werden, indem die Punkte hinzugefügt und/oder gelöscht werden. Das Dynamischer konvexer Rumpf Das Problem besteht darin, den konvexen Rumpf im Auge zu behalten, z. B. für den dynamisch ändernden Satz von Punkten, d. H. Während die Eingangspunkte eingefügt oder gelöscht werden.

Die rechnerische Komplexität für diese Problemklasse wird geschätzt durch:

  • Die Zeit und der Raum, der erforderlich ist, um die Datenstruktur zu konstruieren, die in der Suche nachgefragt werden muss
  • Die Zeit und der Speicherplatz zur Änderung der durchsuchten Datenstruktur nach einer inkrementellen Änderung im Suchraum
  • Die Zeit (und manchmal auch ein zusätzlicher Raum), um eine Frage zu beantworten.

Variationen

Einige Probleme können je nach Kontext als zu einer der Kategorien gehören. Betrachten Sie beispielsweise das folgende Problem.

  • Punkt in Polygon: Entscheiden Sie, ob sich ein Punkt innerhalb oder außerhalb eines bestimmten Polygons befindet.

In vielen Anwendungen wird dieses Problem als Einzelschuss behandelt, d. H. Zu der ersten Klasse gehört. Zum Beispiel in vielen Anwendungen von Computergrafik Ein häufiges Problem besteht darin, herauszufinden, welcher Bereich auf dem Bildschirm von a geklickt wird Zeiger. In einigen Anwendungen ist das betreffende Polygon jedoch unveränderlich, während der Punkt eine Abfrage darstellt. Zum Beispiel kann das Eingangspolygon eine Rand eines Landes darstellen, und ein Punkt ist eine Position eines Flugzeugs, und das Problem besteht darin, festzustellen, ob das Flugzeug gegen die Grenze verstoßen hat. Schließlich im zuvor erwähnten Beispiel von Computergrafiken in CAD Anwendungen Die sich ändernden Eingabedaten werden häufig in dynamischen Datenstrukturen gespeichert, die möglicherweise genutzt werden, um die Punkt-in-Polygon-Abfragen zu beschleunigen.

In einigen Kontexten von Abfrageproblemen gibt es angemessene Erwartungen an die Abfolge der Abfragen, die entweder für effiziente Datenstrukturen oder für strengere Schätzungen der Rechenkomplexität ausgenutzt werden können. In einigen Fällen ist es beispielsweise wichtig, den schlimmsten Fall für die Gesamtzeit für die gesamte Folge von N -Abfragen und nicht für eine einzelne Abfrage zu kennen. Siehe auch "Amortisierte Analyse".

Numerische Computergeometrie

Hauptartikel: Computergestütztes geometrisches Design

Dieser Zweig ist auch als bekannt als Geometrische Modellierung und Computergestütztes geometrisches Design (CAGD).

Kernprobleme sind Kurven- und Oberflächenmodellierung und Darstellung.

Die wichtigsten Instrumente hier sind Parametrische Kurven und Parametrische Oberflächen, wie zum Beispiel Bézier -Kurven, Spline Kurven und Oberflächen. Ein wichtiger nicht parametrischer Ansatz ist der Stufe-Set-Methode.

Anwendungsbereiche der Computergeometrie umfassen Schiffbau-, Flugzeug- und Automobilindustrien.

Siehe auch

Verweise

  1. ^ Franco P. Preparata und Michael Ian Shamos (1985). Computergeometrie - eine Einführung. Springer-Verlag. ISBN 0-387-96131-3. 1. Auflage; 2. Druck, korrigiert und erweitert, 1988.
  2. ^ A.R. Forrest, "Computergeometrie", Proc. Royal Society London, 321, Serie 4, 187-195 (1971)
  3. ^ Yevgeny B. Karasik (2019). Optische Computergeometrie. ISBN 979-8511243344.
  4. ^ S. Khuller und Y. Matias. Ein einfacher randomisierter Siebalgorithmus für das am nächsten Pair-Problem. Inf. Comput., 118 (1): 34—37.1995 (PDF)
  5. ^ S. Fortune und J. E. Hopcroft. "Eine Notiz über Rabins Algorithmus am nächsten Nachbarithmus." Informationsverarbeitungsbriefe, 8 (1), S. 20—23, 1979

Weitere Lektüre

Zeitschriften

Kombinatorische/algorithmische Computergeometrie

Nachfolgend finden Sie die Liste der wichtigsten Zeitschriften, die Forschungen zu geometrischen Algorithmen veröffentlicht haben. Bitte beachten Sie mit dem Auftreten von Zeitschriften, die speziell für die Computergeometrie gewidmet sind, der Anteil geometrischer Veröffentlichungen im Allgemeinen in den Bereichen Informatik- und Computergrafikjournale.

Externe Links