This seminar is offered for students enrolled in the Mathematics Master as module S4C1 as well as students enrolled in the Computer Science Master as module MA-INF 1205. The seminar is organized and held by Prof. Dr. Anne Driemel.

The goal of the seminar is for each participant to:

• Study a scientific paper (see references below)
• Present the main ideas of the paper in a talk (45 minutes excl. questions)
• Participate in discussions on the topic of the seminar
• Submit a written report (in own words) (~10 pages)

The first preparation meeting will take place on Friday 18 July 2025, at 3:15 pm in room 2.074 (Informatik V, 2. OG) . The meeting room is located in the computer science building at Friedrich Hirzebruch Allee 8. The second planning meeting will take place on Wednesday 15 October 2025, at 3:00 pm in the same room.

If you want to participate in the seminar and want to receive updates, please contact Prof. Dr. Anne Driemel with your topic preference from the literature list.

In this seminar we will study the algorithmic complexity of different variants of the shape matching problem. In this problem we are given two shapes in the form of point sets or polygonal curves. The task is to find an optimal translation or other transformation to minimize a shape distance, such as the Fréchet distance, Earth Mover’s distance or Hausdorff distance. We will study approximation algorithms and conditional lower bounds for these problems.

• Aichholzer, O., Alt, H., & Rote, G. (1997). Matching shapes with A reference point. International Journal of Computational Geometry and Applications, 7(4), 349-363. https://doi.org/10.1142/S0218195997000211
• Alt, Helmut, Christian Knauer, and Carola Wenk. “Matching Polygonal Curves with Respect to the Fréchet Distance.” In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, 63–74. STACS ’01. Berlin, Heidelberg: Springer-Verlag, 2001.
• Avraham, Rinat Ben, Haim Kaplan, and Micha Sharir. “A Faster Algorithm for the Discrete Fréchet Distance under Translation.” arXiv, January 15, 2015. https://doi.org/10.48550/arXiv.1501.03724.
• Bringmann, Karl, Marvin Künnemann, and André Nusser. “Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm.” ACM Transactions on Algorithms 17, no. 3 (July 31, 2021): 1–42. https://doi.org/10.1145/3460656.
• Bringmann, Karl, and André Nusser. “Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation.” Application/pdf. Edited by Kevin Buchin and Éric Colin de Verdière. LIPIcs, Volume 189, SoCG 2021 189 (2021): 18:1-18:17. https://doi.org/10.4230/LIPICS.SOCG.2021.18.
• Bringmann, Karl, Frank Staals, Karol Węgrzycki, and Geert van Wordragen. “Fine-Grained Complexity of Earth Mover’s Distance under Translation.” arXiv, March 7, 2024. https://doi.org/10.48550/arXiv.2403.04356.
• Cabello, Sergio, Panos Giannopoulos, Christian Knauer, and Günter Rote. “Matching Point Sets with Respect to the Earth Mover’s Distance.” Computational Geometry 39, no. 2 (February 1, 2008): 118–33. https://doi.org/10.1016/j.comgeo.2006.10.001.
• Chan, Timothy M. “Minimum L∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem.” 39th International Symposium on Computational Geometry, SoCG 2023. https://doi.org/10.4230/LIPIcs.SoCG.2023.24
• Ezra, Esther, Micha Sharir, and Alon Efrat. “On the performance of the ICP algorithm.” Computational Geometry 41.1-2 (2008): 77-93. https://doi.org/10.1016/j.comgeo.2007.10.007