2026-07-25T06:06:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20058 2024-11-27T23:17:43Z ddc:004 open_access

Dynamic L-Budget Clustering of Curves Buchin, Kevin Buchin, Maike Gudmundsson, Joachim Plätz, Lukas Thiel, Lea Wong, Sampson clustering streaming algorithm polygonal curves Fréchet distance storage efficiency simplification approximation algorithms A key goal of clustering is data reduction. In center-based clustering of complex objects therefore not only the number of clusters but also the complexity of the centers plays a crucial role. We propose L-Budget Clustering as unifying perspective on this task, optimizing the clustering under the constraint that the summed complexity of all centers is at most L. We present algorithms for clustering planar curves under the Fréchet distance, but note that our algorithms more generally apply to objects in metric spaces if a notion of simplification of objects is applicable. A scenario in which data reduction is of particular importance is when the space is limited. Our main result is an efficient (8 + ε)-approximation algorithm with a (1 + ε)-resource augmentation that maintains an L-budget clustering under insertion of curves using only O(Lε^{-1}) space and O^*(L³log(L) + L²log(r^*/r₀)) time where O^* hides factors of ε^{-1}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Buchin and Maike Buchin and Joachim Gudmundsson and Lukas Plätz and Lea Thiel and Sampson Wong 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.18 urn:nbn:de:0030-drops-200588 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.18 eng https://creativecommons.org/licenses/by/4.0/legalcode