Algorithmische Geometrie

Wir entwickeln und implementieren Algorithmen zur Lösung geometrischer Probleme, die in verschiedenen Anwendungsgebieten auftreten, z.B. in Computergraphik, geographischen Informationssystemen (GIS) und CAD. Ein wichtiges Kriterium ist dabei für uns die praktische Anwendbarkeit eines Algorithmus. Wir untersuchen, inwieweit bekannte Sekundärspeicherzugriffsmethoden in geometrischen Algorithmen benutzt werden können, wenn die zu verarbeitenden Datenmengen so groß sind, daß sie nicht mehr im Hauptspeicher gehalten werden können. Die in einem Geoinformationssystem (GIS) gespeicherte Information umfaßt geometrische und nicht-geometrische Daten. Die aus der algorithmischen Geometrie bekannten Algorithmen und Datenstrukturen können nicht direkt in Geoinformationssystemen angewendet werden, da sie die Verarbeitung nicht- geometrischer Daten nicht unterstützen. Wir entwickeln neue Datenstrukturen zur Speicherung von Karten, die durch planare Unterteilungen dargestellt werden können, und effiziente Algorithmen zur Durchführung der Kartenverschneidung und anderer GIS-Operationen. Im Rahmen ihres Schwerpunktprogramms "Effiziente Algorithmen für diskrete Probleme und ihre Anwendungen" fördert die DFG unser Projekt "Vektororientierte und hybride Verschneidungsalgorithmen für Geoinformationssysteme".

Beteiligte Wissenschaftler:

Dipl.-Math. A. Brinkmann, Prof. Dr. K. Hinrichs, Dipl.-Math. J. Vahrenhold

Veröffentlichungen:

Brinkmann, A., K. Hinrichs: Implementing Exact Line Segment Intersection in Map Overlay, Proc. of the 8th Intern. Symposium on Spatial Data Handling SDH 98, Vancouver, 569-579, 1998

Vahrenhold, J., K. Hinrichs: Fast and Simple External-Memory Planar Point-Location, Abstracts of the 14th European Workshop on Computational Geometry (CG'98), F. Hurtado, J. Trias (Eds.), Universitat Politecnica de Catalunya (1998), 139-140