TY - JOUR
AU - Brüning, Frederik
AU - Akitaya, Hugo
AU - Chambers, Erin
AU - Driemel, Anne
PY - 2023/02/23
Y2 - 2024/06/23
TI - Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves
JF - Computing in Geometry and Topology
JA - CompGeomTop
VL - 2
IS - 1
SE - Original Research Articles
DO - 10.57717/cgt.v2i1.7
UR - https://cgt-journal.org/index.php/cgt/article/view/7
SP - 1:1-1:48
AB - <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>
ER -