2026-08-06T13:13:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23510 2025-10-02T12:57:19Z ddc:004 open_access

Faster, Deterministic and Space Efficient Subtrajectory Clustering van der Hoog, Ivor van der Horst, Thijs Ophelders, Tim Fréchet distance clustering set cover 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échet distance Δ to at least one curve in C. We call C an (𝓁,Δ)-clustering and aim to find an (𝓁,Δ)-clustering of minimum cardinality. This problem variant was introduced by Akitaya et al. (2021) and shown to be NP-complete. The main focus has therefore been on bicriteria approximation algorithms, allowing for the clustering to be an (𝓁, Θ(Δ))-clustering of roughly optimal size. We present algorithms that construct (𝓁,4Δ)-clusterings of 𝒪(k log n) size, where k is the size of the optimal (𝓁, Δ)-clustering. We use 𝒪(n³) space and 𝒪(k n³ log⁴ n) time. Our algorithms significantly improve upon the clustering quality (improving the approximation factor in Δ) and size (whenever 𝓁 ∈ Ω(log n / log k)). We offer deterministic running times improving known expected bounds by a factor near-linear in 𝓁. Additionally, we match the space usage of prior work, and improve it substantially, by a factor super-linear in n𝓁, when compared to deterministic results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ivor van der Hoog and Thijs van der Horst and Tim Ophelders 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.133 urn:nbn:de:0030-drops-235109 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.133 eng https://creativecommons.org/licenses/by/4.0/legalcode