k-Median clustering under discrete Fréchet and Hausdorff distances

Abhinandan Nath, Erin Taylor

We give the first near-linear time $(1+\eps)$-approximation algorithm for $k$-median clustering of polygonal trajectories under the discrete Fréchet distance, and the first polynom…