@article{Brüning_Akitaya_Chambers_Driemel_2023, title={Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves}, volume={2}, url={https://www.cgt-journal.org/index.php/cgt/article/view/7}, DOI={10.57717/cgt.v2i1.7}, abstractNote={<p>We study subtrajectory clustering under the Fréchet 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 Δ > 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échet distance to one of the k center curves (≤ Δ). 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 Δ, then our algorithm finds a set of k’ center curves of complexity at most ℓ with covering radius Δ’ with k’ in O(kℓ<sup>2</sup> log (kℓ)), and Δ’ ≤ 19Δ. 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 Δ is constant. In this case, the algorithm has expected running time in Õ(km<sup>2</sup> + mn) and uses space in O(n + m), where m=⌈L/Δ⌉ and L is the total arclength of the curve P.</p>}, number={1}, journal={Computing in Geometry and Topology}, author={Brüning, Frederik and Akitaya, Hugo and Chambers, Erin and Driemel, Anne}, year={2023}, month={Feb.}, pages={1:1–1:48} }