Parallel algorithms in computational geometry with an emphasis on pattern recognition
Final Report Abstract
Ziel des Projekts war es, parallele Algorithmen für Probleme der algorithmischen Geometrie mit Schwerpunkt im Bereich der geometrischen Mustererkennung und Formanpassung zu entwickeln. Dazu betrachteten wir zunächst allgemeinere Probleme der algorithmischen Geometrie und Algorithmenentwurfstechniken, die als Bausteine in den Algorithmen zur geometrischen Mustererkennung häufig vorkommen. Im ersten Teil des Projekts haben wir parallele Algorithmen für allgemeine Probleme der algorithmischen Geometrie sowie für spezielle, durch die Mustererkennung motivierte Probleme entwickelt. Diese wurden, oft in studentischen Arbeiten, implementiert, wobei meist OpenCL als Programmierumgebung eingesetzt und dabei GPGPU (general purpose usage of graphics processing unit) benutzt wurde. Wir gehen auf diese Algorithmen und Techniken hier nur ein, soweit sie im zweiten Teil des Projekts weiterbearbeitet wurden. Insbesondere wurde im zweiten Teil am Entwurf sowie der Implementierung eines parallelen Algorithmus zur Berechnung der “Tiefe” der Zellen einer ebenen Unterteilung durch eine Menge von Rechtecken weitergearbeitet. Dies geschah in Zusammenarbeit mit Prof. Hagerup von der Universität Augsburg.
Publications
-
Approximating Smallest Containers for Packing Three-Dimensional Convex Objects. In In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC), pages 11:1–11:14, 2016
Helmut Alt and Nadja Scharf
-
Polynomial Time Approximation Schemes for Circle Packing Problems. In In Proceedings of the 33th European Workshop on Computational Geometry (EuroCG), 2017
Helmut Alt and Nadja Scharf
-
Approximating Smallest Containers for Packing Three-Dimensional Convex Objects. Int. J. Comput. Geometry Appl., 28(2):111–128, 2018
Helmut Alt and Nadja Scharf
-
Packing 2D Disks into a 3D Container. In In Proceedings of the 13th International Conference and Workshops on Algorithms and Computation (WALCOM), pages 369–380, 2019
Helmut Alt, Otfried Cheong, Ji-won Park, and Nadja Scharf
