Faster and Deterministic Subtrajectory Clustering

Abstract

We study the subtrajectory clustering problem. Given a trajectory $T$, the goal is to identify a set of subtrajectories such that each point on $T$ is included in at least one subtrajectory, and subsequently group these subtrajectories together based on similarity under the Fréchet distance. We wish to minimize the set of groups. This problem was shown to be NP-complete by Akitaya, Brüning, Chambers, and Driemel (2021), and the focus has mainly been on approximation algorithms. We study a restricted variant, where we may only pick subtrajectories that start and end at vertices of $T$, and give an approximation algorithm that significantly improves previous algorithms in both running time and space, whilst being deterministic.