Gesellschaft für Informatik - Fachgruppe 0.1.2
Algorithmische Geometrie

Ziele der Fachgruppe

Die algorithmische Geometrie hat sich in den letzten 15 Jahren als aktives Forschungsgebiet innerhalb der theoretischen Informatik etabliert. Ziel der Fachgruppe ist es, ein Forum für diese Interessenten -- wenn möglich auch über Deutschland hinaus -- zu bilden, und durch mehrere Aktivitäten die Forschungen auf diesem Gebiet zu unterstützen. Neben der Förderung der Grundlagenforschung soll die Fachgruppe auch stärkere Verbindungen zu den zahlreichen Anwendungsgebieten der algorithmischen Geometrie -- wie etwa Computer-Graphik, Robotik, VLSI-Design, Operations Research etc. -- sowie zu verwandten Gebieten der Mathematik -- wie etwa Geometrie, Kombinatorik, Kombinatorische Optimierung etc. -- ermöglichen.

Die algorithmische Geometrie beschäftigt sich ,,traditionellerweise`` mit Problemen auf großen Mengen geometrischer Objekte in kleinen Dimensionen. Die Algorithmen und Methoden lassen sich zwar oft auf beliebig hohe Dimension verallgemeinern, verlieren aber sehr schnell an Effizienz. In letzter Zeit wird auch in diesem Gebiet zunehmend Augenmerk auf höhere Dimensionen und Implementierungsgesichtspunkte gelegt.

Typische Probleme sind etwa die Berechnung konvexer Hüllen von Punkten, Konstruktionen von Voronoi-Diagrammen, Schnittprobleme auf geometrischen Objekten (Welche Paare von n Liniensegmenten schneiden sich?), Bereichsabfrageprobleme (Welche von gegebenen n Objekten liegen in einem Abfragerechteck?), etc.

Im folgenden sollen -- ohne Anspruch auf Vollständigkeit -- kurz einige Schwerpunkte benannt werden, wie sie derzeit am aktivsten untersucht werden.

  1. Grundlegende Methoden und Verfahren.
    Allgemeine geometrische Algorithmen und Datenstrukturen, Such- und Abfrageprobleme, Berechnung von Durchschnitten, geometrische Transformationen, Arrangements von Hyperebenen, konvexe und nichtkonvexe nichtnumerische geometrische Optimierungsprobleme, Lineares (und konvexes) Programmieren mit wenigen Variablen, randomisierte Algorithmen.
  2. Anwendungsgebiet Robotik.
    Bewegungsplanung, Sichtbarkeitsprobleme, Kollisionsvermeidung, Distanzprobleme, Probleme beim Greifen mit Roboterhänden.
  3. Anwendungsgebiet Computer-Graphik.
    Hidden Surface Removal, Strahlverfolgungsalgorithmen.
  4. Anwendungsgebiet Computerunterstütztes Entwerfen (CAD).
    Zerlegung von Polytopen, Triangulierungen im Raum, (Re-)Konstruktion von Objekten.
  5. Anwendungsgebiet Geodatenbanken.
    Externspeicherung großer Mengen geometrischer Daten, effiziente Zugriffe über geometrische und Standardattribute.
  6. Implementierung geometrischer Datenstrukturen und Algorithmen.
    Beschreibung geometrischer Objekte, Perturbierungstechniken, Testdatenerstellung, Rechnen mit ,,unendlicher Genauigkeit`` (infinite precision), Vergleich und Bewertung von Software.

Es ist geplant, Kontakte zu mehreren Fachgruppen der GI zu knüpfen, um die Anwendung der erzielten Ergebnisse zu forcieren und neue interessante und wichtige Fragestellungen kennenzulernen. Es bieten sich hier an:

In diesem Zusammenhang sind Seminare mit Anwendern vorgesehen. Weitere Kooperationen bieten sich mit der Gesellschaft für Operations Research und der DMV an (auf Gebieten wie Kombinatorische Optimierung, Kombinatorik, Geometrie). Weiterhin ist geplant, bestehende Veranstaltungen wie den European Workshop über Computational Geometry (CG), oder etwa das Dagstuhl-Seminar über algorithmische Geometrie in Kooperation mit der Fachgruppe zu organisieren.

Zur Hauptseite der GI-Fachgruppe 0.1.2 Algorithmische Geometrie


Letzte Änderung am 16. April 2003 von Christian.Icking@fernuni-hagen.de.