Faster and Deterministic Subtrajectory Clustering

Given a trajectory T and a distance, we wish to find a set C of curves of complexity at most, such that we can cover T with subcurves that each are within Fr\'echet distance to at least one curve in C. We call C an (, ) -clustering and aim to find an (, ) -clustering of minimum cardinality. This problem was introduced by Akitaya et al. (2021) and shown to be NP-complete. The main focus has therefore been on bicriterial approximation algorithms, allowing for the clustering to be an (, () ) -clustering of roughly optimal size. We present algorithms that construct (, 4) -clusterings of O (k n) size, where k is the size of the optimal (, ) -clustering. For the discrete Fr\'echet distance, we use O (n n) space and O (k n² ³ n) deterministic worst case time. For the continuous Fr\'echet distance, we use O (n² n) space and O (k n³ ³ n) time. Our algorithms significantly improve upon the clustering quality (improving the approximation factor in) and size (whenever (n) ). We offer deterministic running times comparable to known expected bounds. Additionally, in the continuous setting, we give a near-linear improvement upon the space usage. When compared only to deterministic results, we offer a near-linear speedup and a near-quadratic improvement in the space usage. When we may restrict ourselves to only considering clusters where all subtrajectories are vertex-to-vertex subcurves, we obtain even better results under the continuous Fr\'echet distance. Our algorithm becomes near quadratic and uses space that is near linear in n.