4 papers
The Quick Dog Jumps the Log
Lotte Blank, Anne Driemel, Anne Drieme +2
We give linear-time, and thus optimal, -approximation algorithms for numerous variants of the Frechet distance between -packed curves (where ), remo…
Optimal Metric Distortion for Learning-Augmented Matching on the Line
Jabari Hastings, Marena Richter
We revisit the problem of matching on the line with ordinal preferences. In the classic setting, there are agents and items in a shared unknown line metric, and the goal is…
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 gi…
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 s…