1 citations · 1 across the 3 of their papers we have counts for
7 papers · 1 filter
The Quick Dog Jumps the Log
Lotte Blank, Anne Driemel, Sariel Har-Peled +1
We give linear-time, and thus optimal, -approximation algorithms for numerous variants of the Frechet distance between -packed curves (where ), remo…
Fine-Grained Complexity of Continuous Euclidean k-Center
Lotte Blank, Karl Bringmann, Parinya Chalermsook +4
In the (continuous) Euclidean -center problem, given points in and an integer , the goal is to find center points in that minimize the m…
Fréchet Distance in the Imbalanced Case
Lotte Blank
Given two polygonal curves and defined by and vertices with , we show that the discrete Fréchet distance in 1D cannot be approximated within a factor of $2…
Bicriteria Polygon Aggregation with Arbitrary Shapes
Lotte Blank, David Eppstein, Jan-Henrik Haunert +6
We study the problem of aggregating a set of polygons by covering them with disjoint representative regions, thereby inducing a clustering of the polygons. Equivalently, this can b…
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…