The Fréchet distance mathematically formalizes a notion of similarity or distance for curves. It is similar to the well-known Hausdorff distance for sets, but it in contrast to the Hausdorff distance, it takes the ordering of the points along the curves into account. One can intuitively define the distance measure as follows. Imagine walking forwards along the two curves simultaneously with varying speeds. The maximum distance between the two paired points on the curves over the entire walk is called the cost of the walk. The Fréchet distance is the minimal cost of a walk that traverses both curves from beginning to end without backtracking along the curves.

Clustering is a fundamental task in data analysis. We study efficient algorithms for center-based clustering under the Fréchet distance with the additional requirement that the center curves should be of low complexity. We study the computational complexity of this problem. We show that the problem (with or without this restriction) is NP-hard to approximate within a constant factor. Forthermore, we study probabilistic (1+eps)-approximation algorithms and efficient heuristics in practice. An important problem variant is subtrajectory clustering, where we are interested in an optimal subdivision of the curves into a set of shorter subcurves that admits a clustering.

• Maike Buchin, Anne Driemel, Dennis Rohde: Approximating (k,l)-Median Clustering for Polygonal Curves. SODA 2021: 2697-2717
• Kevin Buchin, Anne Driemel, Martijn Struijs: On the Hardness of Computing an Average Curve. SWAT 2020: 19:1-19:19
• Kevin Buchin, Anne Driemel, Natasja van de L'Isle, André Nusser: klcluster: Center-based Clustering of Trajectories. SIGSPATIAL/GIS 2019: 496-499
• Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler, Martijn Struijs: Approximating (k,l)-center clustering for curves. SODA 2019: 2922-2938
• Anne Driemel, Amer Krivosija, Christian Sohler: Clustering time series under the Fréchet distance. SODA 2016: 766-785

Data structures for proximity searching are well-studied in computational geometry. Given a set of input elements from a metric space, the task is to preprocess them into a data structure that supports (approximate) nearest neighbor queries. We study this problem for polygonal curves where the metric is given by the Fréchet distance. We are interested in lower bounds on the tradeoffs between space complexity, query time, and approximation factor of attainable data structures, as well as upper bounds that match these lower bounds in the important problem parameters, such as number of input curves, complexity of the input curves, and the complexity of supported query curves. An interesting and important problem variant is concerned with range searching. Here, a range is a subset of a metric space that is specified with the query. A range query may asks for certain statistics derived from the set of input curves contained in the query range, for example, the number of input curves contained in the range.

• Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros: Tight bound for the approximate near-neighbor problem for time series under the Frechet distance. SODA 2022 (to appear)
• Anne Driemel, Ioannis Psarros: ANN for time series under the Fréchet distance. Algorithms and Data Structures Symposium 2021. (to appear)
• Anne Driemel, Jeff M. Phillips, Ioannis Psarros: The VC Dimension of Metric Balls Under Fréchet and Hausdorff Distances. Symposium on Computational Geometry 2019: 28:1-28:16
• Peyman Afshani, Anne Driemel: On the complexity of range searching among curves. SODA 2018: 898-917
• Anne Driemel, Francesco Silvestri: Locality-Sensitive Hashing of Curves. Symposium on Computational Geometry 2017: 37:1-37:16

In the field of computer vision, tracking and forecasting are closely related problems. This is in particular the case, when multiple objects need to be tracked across several frames in the presence of occlusions, and when the objects to be tracked do not carry markers that would easily identify them. Consequently, there exists a lot of computer vision literature on trajectory forecasting with the focus on reliable short-term forecasting that enables the tracking of a visible object across multiple frames. However, the problem of forecasting trajectories is much more fundamental and has many applications beyond tracking, e.g., in risk assessment, anomaly detection, crowd simulation and collision avoidance. It remains a challenging task, even when separated from the tracking task, e.g., when the tracking is provided through location sensors or other reliable means of estimating the location of a moving object. In this project we take a fundamental look at the computational challenges underlying the trajectory forecasting task, for short-term as well as long-term forecasting. In the process, we aim to transfer ideas and methods from the field of computational geometry and shape matching to advance the field of trajectory forecasting. To this end, we want to develop a unified model for hierarchical representations of trajectories spanning dimension reduction, simplification and clustering under a suitable similarity measure, such as the Fréchet distance. Secondly, we want to investigate data structures for similarity search under partial similarity, and thirdly we want to initiate a fundamental study of trajectory segmentation based on subtrajectory clustering.

The project Forecasting Trajectories is embedded in DFG Research unit “Anticipating Human Behavior” (FOR 2535) (Second Phase)

Anne Driemel