# Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves

arXiv: https://arxiv.org/abs/2103.06040 · HTML: https://mlsanity.com/paper/2103.06040/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2021.

## Built on by (most cited first, 1 of 1)

- [TiVy: Time Series Visual Summary for Scalable Visualization](https://mlsanity.com/paper/2507.18972/) (2025)

## Abstract (arXiv)

We study subtrajectory clustering under the Fr'echet distance. Given one or more trajectories, the task is to split the trajectories into several parts, such that the parts have a good clustering structure. We approach this problem via a new set cover formulation, which we think provides a natural formalization of the problem as it is studied in many applications. Given a polygonal curve P with n vertices in fixed dimension, integers k, ℓ ≥ 1, and a real value Delta > 0, the goal is to find k center curves of complexity at most ℓ such that every point on P is covered by a subtrajectory that has small Fr'echet distance to one of the k center curves (≤ Delta). In many application scenarios, one is interested in finding clusters of small complexity, which is controlled by the parameter ℓ. Our main result is a bicriterial approximation algorithm: if there exists a solution for given parameters k, ℓ, and Delta, then our algorithm finds a set of k' center curves of complexity at most ℓ with covering radius Delta' with k' ∈ O( k ℓ2 log (k ℓ)), and Delta'≤ 19 Delta. Moreover, within these approximation bounds, we can minimize k while keeping the other parameters fixed. If ℓ is a constant independent of n, then, the approximation factor for the number of clusters k is O(log k) and the approximation factor for the radius Delta is constant. In this case, the algorithm has expected running time in  tildeOleft( k m2 + mnright) and uses space in O(n+m), where m=lceilfracLDeltarceil and L is the total arclength of the curve P.