Dynamic L-Budget Clustering of Curves
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Accepted author manuscript, 1.22 MB, PDF document
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 LBudget 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∗(L3 log L + L2 log(r∗/r0)) time where O∗ hides factors of ε−1
Original language | English |
---|---|
Title of host publication | 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024 |
Editors | Hans L. Bodlaender |
Number of pages | 17 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | Jun 2024 |
Article number | 18 |
ISBN (Electronic) | 9783959773188 |
DOIs | |
Publication status | Published - Jun 2024 |
Event | 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024 - Helsinki, Finland Duration: 12 Jun 2024 → 14 Jun 2024 |
Conference
Conference | 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024 |
---|---|
Land | Finland |
By | Helsinki |
Periode | 12/06/2024 → 14/06/2024 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 294 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong; licensed under Creative Commons License CC-BY 4.0.
- approximation algorithms, clustering, Fréchet distance, polygonal curves, simplification, storage efficiency, streaming algorithm
Research areas
ID: 395153652