Faster and Deterministic Subtrajectory Clustering

Research output: Contribution to conferencePaperAcademic


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.
Original languageEnglish
Number of pages7
Publication statusPublished - 2024
Event40th European Workshop on Computational Geometry (EuroCG 2024) - Ioannina, Greece
Duration: 13 Mar 202415 Mar 2024


Conference40th European Workshop on Computational Geometry (EuroCG 2024)


Dive into the research topics of 'Faster and Deterministic Subtrajectory Clustering'. Together they form a unique fingerprint.

Cite this