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 language | English |
|---|---|
| Pages | 41:1-41:7 |
| Number of pages | 7 |
| Publication status | Published - 2024 |
| Event | 40th European Workshop on Computational Geometry (EuroCG 2024) - Ioannina, Greece Duration: 13 Mar 2024 → 15 Mar 2024 |
Conference
| Conference | 40th European Workshop on Computational Geometry (EuroCG 2024) |
|---|---|
| Country/Territory | Greece |
| City | Ioannina |
| Period | 13/03/24 → 15/03/24 |
Bibliographical note
40th European Workshop on Computational Geometry, Ioannina, Greece, March 13–15, 2024.This is an extended abstract of a presentation given at EuroCG’24.