35 citations · 91 across the 28 of their papers we have counts for
36 papers · 1 filter
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…
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…
Approximating -Median Clustering for Polygonal Curves
Maike Buchin, Anne Driemel, Dennis Rohde
In 2015, Driemel, Krivošija and Sohler introduced the -median problem for clustering polygonal curves under the Fréchet distance. Given a set of input curves, the problem…
-ANN for time series under the Fréchet distance
Anne Driemel, Ioannis Psarros
We study approximate-near-neighbor data structures for time series under the continuous Fréchet distance. For an attainable approximation factor and a query radius , an ap…
Sublinear data structures for short Fréchet queries
Anne Driemel, Ioannis Psarros, Melanie Schmidt
We study metric data structures for curves in doubling spaces, such as trajectories of moving objects in Euclidean , where the distance between two curves is measured…
The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances
Anne Driemel, André Nusser, Jeff M. Phillips +1
The Vapnik-Chervonenkis dimension provides a notion of complexity for systems of sets. If the VC dimension is small, then knowing this can drastically simplify fundamental computat…
On the hardness of computing an average curve
Kevin Buchin, Anne Driemel, Martijn Struijs
We study the complexity of clustering curves under -median and -center objectives in the metric space of the Fréchet distance and related distance measures. Building upon rec…