Driemel Group

We have a broad interest in algorithmic problems involving geometry. Our primary goal is to design algorithms and data structures that are both practical and have provable performance. To this end, we combine the classical worst-case analysis with approximation and randomization techniques and with realistic input assumptions. Both techniques, approximation and randomization, are useful to obtain simple algorithmic solutions that are effective in practice. Our recent work is motivated by data analysis in spaces of curves, where we aim to solve classical problems such as clustering and nearest-neighbor searching under alignment-based distance measures, such as the continuous Fréchet metric and Dynamic Time Warping.

Discover our homepage here.

Methods

• Algorithms and Datastructures
• Discrete and combinatorial geometry
• Computational trajectory analysis

5 selected publications

1. Bringmann, Karl, Anne Driemel, André Nusser, and Ioannis Psarros. “Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance.” In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 517-550. Society for Industrial and Applied Mathematics, 2022.
2. Buchin, Maike, Anne Driemel, and Dennis Rohde. “Approximating (k,l)-Median Clustering for Polygonal Curves.” In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2697-2717. Society for Industrial and Applied Mathematics, 2021.
3. Buchin, Kevin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler, and Martijn Struijs. “Approximating (k, ℓ)-center clustering for curves.” In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2922-2938. Society for Industrial and Applied Mathematics, 2019.
4. Afshani, Peyman, and Anne Driemel. “On the complexity of range searching among curves.” In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 898-917. Society for Industrial and Applied Mathematics, 2018.
5. Driemel, Anne, Amer Krivošija, and Christian Sohler. “Clustering time series under the Fréchet distance.” In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp. 766-785. Society for Industrial and Applied Mathematics, 2016.