BARC talk by Lotte Blank

Tuesday, September 8, 2026, 15:15-16:15, Lotte Blank, PhD student at the University of Bonn, Germany, will be giving a BARC talk on "Fréchet Distance in the Imbalanced Case".

Abstract:
The Fréchet distance is a similarity measure between polygonal curves defined by $n$ and $m$ vertices. Classical algorithms to compute the Fréchet distance exactly run in $\widetilde{O}(nm)$ time, and this talk focuses on recent results for the special case where $m=n^\alpha$ with $\alpha\in(0,1)$. We begin with a simple $(3+\varepsilon)$-approximation algorithm that runs in $\widetilde{O}(n+m^2)$ time. We then show that stronger results are possible for one-dimensional curves within essentially the same running time: for the discrete Fréchet distance, there is an optimal $2$-approximation algorithm, and surprisingly, for the continuous Fréchet distance in 1D, there is even an exact algorithm within this time bound. These one-dimensional running times are optimal up to logarithmic factors.

Bio:
Lotte Blank is a PhD student in computational geometry at the University of Bonn, supervised by Anne Driemel. After completing her bachelor’s and master’s degrees in mathematics, she joined the Theoretical Computer Science group in Bonn. Her primary research focuses on curve similarity measures, including problems such as range searching among curves, Fréchet distance under translation and scaling, realistic input curves, and imbalanced input complexities; for her work on the Fréchet distance in the imbalanced case, she received the Best Student Paper Award at SoCG 2026. Her broader research interests include clustering algorithms, streaming algorithms, and fine-grained complexity.

Host:
Jacobus Conradi