Faster and Deterministic Subtrajectory Clustering

Research output: Contribution to conferencePaperAcademic

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

Conference

Conference40th European Workshop on Computational Geometry (EuroCG 2024)
Country/TerritoryGreece
CityIoannina
Period13/03/2415/03/24

Cite this