2024/02/20 by van der Hoog, Ivor, van der Horst, Thijs, Ophelders, Tim · 1 citation
#Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2402.13117
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 O(k log n) size, where k is the size of the optimal (ℓ, Δ)-clustering. We use O(n3) space and O(k n3 log4 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.