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.

Beteiligte Wissenschaftler:

Dipl.-Math. Andreas Brinkmann, Prof. Dr. Klaus Hinrichs, Dipl.-Math. Jan 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 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 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

Lars Arge, Klaus H. Hinrichs, Jan Vahrenhold, and Jeffrey S. Vitter: Efficient Bulk Operations on Dynamic R-trees. In: Catherine C. McGeoch and Michael T. Goodrich, editors, Proceedings of the First Workshop on Algorithm Engineering and Experimentation (ALENEX '99), volume 1619 of Lecture Notes in Computer Science, pages 328-347. Springer, Berlin, 1999. © Springer-Verla

Ludger Becker, André Giesen, Klaus H. Hinrichs, and Jan Vahrenhold: Algorithms for Performing Map Overlay and Spatial Join for Massive Data Sets. In: Ralf Hartmut Güting, Dimitris Papadias, and Fred Lochovsky, editors, Advances in Spatial Databases - Proceedings of the Sixth International Symposium on Spatial Databases (SSD '99), volume 1651 of Lecture Notes in Computer Science, pages 270-285. Springer, Berlin, 1999. Springer-Verlag

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, and Jeffrey S. Vitter: A Unified Appraoch for Indexed and Non-Indexed Spatial Joins. In: Carlo Zaniolo, Peter C. Lockemann, Marc H. Scholl, and Torsten Grust, editors, Advances in Database Technology - Proceedings of the 7th International Conference on Extending Database Technology (EDBT '00), volume 1777 of Lecture Notes in Computer Science, pages 413-429. Springer, Berlin, 2000.

Lars Arge and Jan Vahrenhold: I/O-Efficient Dynamic Planar Point-Location. In Proceedings of the 16th Annual ACM Symposium on Computational Geometry (SCG '00), pages 191-200. ACM Press, 2000.

Jan Vahrenhold and Klaus H. Hinrichs: Planar Point Location for Large Data Sets: To Seek or Not To Seek. In: Stefan Näher and Dorothea Wagner, editors, Proceedings of the Fourth Workshop on Algorithm Engineering (WAE 2000), Lecture Notes in Computer Science, (to appear). Springer, Berlin, 2000.

Jan Vahrenhold: External Memory Algorithms for Geographic Information Systems, Dissertation, 1999