Parallel algorithms in computational geometry with an emphasis on pattern recognition

• Applicant: Professor Dr. Helmut Alt
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 166649592

• Final Report Year: 2020

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
  (See online at https://doi.org/10.4230/LIPIcs.ISAAC.2016.11)
• 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
  (See online at https://doi.org/10.4230/LIPIcs.ISAAC.2016.11)
• 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
  (See online at https://doi.org/10.1007/978-3-030-10564-8_29)