Parallele Algorithmen in der algorithmischen Geometrie mit dem Schwerpunkt auf Mustererkennung

• Antragsteller: Professor Dr. Helmut Alt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 166649592

• Erstellungsjahr: 2020

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter https://doi.org/10.1007/978-3-030-10564-8_29)