Covering a Curve with Subtrajectories.
Hugo A. Akitaya, Frederik Brüning, Erin Wolf Chambers, Anne Driemel · arXiv (Cornell University) · 2021
We study subtrajectory clustering under the Frechet distance. Given a polygonal curve $P$ with $n$ vertices, and parameters $k$ and $\ell$, the goal is to find $k$ center curves of complexity at most $\ell$ such that every point on $P$ is covered by a subtrajectory that has small Frechet distance to one of the $k$ center curves. We suggest a new approach to solving this problem based on a set cover formulation leading to polynomial-time approximation algorithms. Our solutions rely on carefully designed set system oracles for systems of subtrajectories.