35 citations · 91 across the 28 of their papers we have counts for
41 papers
Time Series Decomposition using the Fréchet Distance
Anne Driemel, Jan Höckendorff, Ioannis Psarros +1
In this paper, we introduce a new data analysis problem that aims to decompose a set of univariate time series into a small set of base curves of length at most such that t…
Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
Anne Driemel, Jan Höckendorff, Ioannis Psarros +2
Given a finite metric space the -median problem is to find a set of centers that minimizes $\sum_{p\in X} \min_{c\in C} \mathbf{d}(p,c…
A near-linear time approximation scheme for -median clustering under discrete Fréchet distance
Anne Driemel, Jan Höckendorff, Ioannis Psarros +1
A time series of complexity is a sequence of real valued measurements. The discrete Fréchet distance is a distance measure between two time series and …
Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better
Jacobus Conradi, Anne Driemel
Many application areas collect unstructured trajectory data. In subtrajectory clustering, one is interested to find patterns in this data using a hybrid combination of segmentation…
Range Counting Oracles for Geometric Problems
Anne Driemel, Morteza Monemizadeh, Eunjin Oh +2
In this paper, we study estimators for geometric optimization problems in the sublinear geometric model. In this model, we have oracle access to a point set with size in a disc…
Property Testing of Curve Similarity
Peyman Afshani, Maike Buchin, Anne Driemel +2
We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is giv…
Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D
Lotte Blank, Jacobus Conradi, Anne Driemel +3
The Fréchet distance is a computational mainstay for comparing polygonal curves. The Fréchet distance under translation, which is a translation invariant version, considers the sim…
A faster algorithm for the Fréchet distance in 1D for the imbalanced case
Lotte Blank, Anne Driemel
The fine-grained complexity of computing the Fréchet distance has been a topic of much recent work, starting with the quadratic SETH-based conditional lower bound by Bringmann from…
On the number of iterations of the DBA algorithm
Frederik Brüning, Anne Driemel, Alperen Ergür +1
The DTW Barycenter Averaging (DBA) algorithm is a widely used algorithm for estimating the mean of a given set of point sequences. In this context, the mean is defined as a point s…
Range Reporting for Time Series via Rectangle Stabbing
Lotte Blank, Anne Driemel
We study the Fréchet queries problem. It is a data structure problem, where we are given a set of polygonal curves and a distance threshold . The data structure should s…
Revisiting the Fréchet distance between piecewise smooth curves
Jacobus Conradi, Anne Driemel, Benedikt Kolbe
Since its introduction to computational geometry by Alt and Godau in 1992, the Fréchet distance has been a mainstay of algorithmic research on curve similarity computations. The fo…
Finding Complex Patterns in Trajectory Data via Geometric Set Cover
Jacobus Conradi, Anne Driemel
Clustering trajectories is a central challenge when faced with large amounts of movement data such as GPS data. We study a clustering problem that can be stated as a geometric set…
Solving Proximity Problems for Polygonal Shapes via Polynomials
Frederik Brüning, Siu-Wing Cheng, Anne Driemel +1
We study range spaces, where the ground set consists of either polygonal curves in or polygonal regions in the plane that may contain holes and the ranges are balls…
-ANN Data Structure for Curves via Subspaces of Bounded Doubling Dimension
Jacobus Conradi, Anne Driemel, Benedikt Kolbe
We consider the -Approximate Nearest Neighbour (ANN) Problem for polygonal curves in -dimensional space under the Fréchet distance and ask to what extent known…
Analysis of a Greedy Heuristic for the Labeling of a Map with a Time-Window Interface
Annika Bonerath, Anne Driemel, Jan-Henrik Haunert +3
In this paper, we analyze the approximation quality of a greedy heuristic for automatic map labeling. As input, we have a set of events, each associated with a label at a fixed pos…
Pattern matching under DTW distance
Garance Gourdel, Anne Driemel, Pierre Peterlongo +1
In this work, we consider the problem of pattern matching under the dynamic time warping (DTW) distance motivated by potential applications in the analysis of biological data produ…
Faster Approximate Covering of Subcurves under the Fréchet Distance
Frederik Brüning, Jacobus Conradi, Anne Driemel
Subtrajectory clustering is an important variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are…
Minimum-Error Triangulations for Sea Surface Reconstruction
Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert +6
We apply state-of-the-art computational geometry methods to the problem of reconstructing a time-varying sea surface from tide gauge records. Our work builds on a recent article by…
On Computing the -Shortcut Fréchet Distance
Jacobus Conradi, Anne Driemel
The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min-max formulation that considers all direction-preserving continuous bijection…
On the Discrete Fréchet Distance in a Graph
Anne Driemel, Ivor van der Hoog, Eva Rotenberg
The Fréchet distance is a well-studied similarity measure between curves that is widely used throughout computer science. Motivated by applications where curves stem from paths and…
Approximating Length-Restricted Means under Dynamic Time Warping
Maike Buchin, Anne Driemel, Koen van Greevenbroek +2
We study variants of the mean problem under the -Dynamic Time Warping (-DTW) distance, a popular and robust distance measure for sequential data. In our setting we are given…
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance
Karl Bringmann, Anne Driemel, André Nusser +1
We study the -approximate near neighbor problem under the continuous Fréchet distance: Given a set of polygonal curves with vertices, a radius , and a parameter $k…
Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves
Hugo A. Akitaya, Frederik Brüning, Erin Chambers +1
We study subtrajectory clustering under the Fréchet distance. Given one or more trajectories, the task is to split the trajectories into several parts, such that the parts have a g…
Spatio-Temporal Top-k Similarity Search for Trajectories in Graphs
Lutz Oettershagen, Anne Driemel, Petra Mutzel
We study the problem of finding the most similar trajectories to a given query trajectory. Our work is inspired by the work of Grossi et al. [6] that considers trajectories as…