The Quick Dog Jumps the Log

Lotte Blank, Anne Driemel, Anne Drieme +2

We give linear-time, and thus optimal, $(1+\epsilon )$-approximation algorithms for numerous variants of the Frechet distance between $c$-packed curves (where $c\in O(1)$), remo…