City Research Online

On k-means for segments and polylines

Cabello, S. & Giannopoulos, P. ORCID: 0000-0002-6261-1961 (2023). On k-means for segments and polylines. In: 31st Annual European Symposium on Algorithms (ESA 2023). ESA 2023, 4-6 Sep 2023, Amsterdam, the Netherlands. doi: 10.4230/LIPIcs.ESA.2023.28

Abstract

We study the problem of k-means clustering in the space of straight-line segments in R² under the Hausdorff distance. For this problem, we give a (1 + ε)-approximation algorithm that, for an input of n segments, for any fixed k, and with constant success probability, runs in time O(n + ε−O(k) + ε−O(k)· logO(k)(ε−1)). The algorithm has two main ingredients. Firstly, we express the k-means objective in our metric space as a sum of algebraic functions and use the optimization technique of Vigneron [40] to approximate its minimum. Secondly, we reduce the input size by computing a small size coreset using the sensitivity-based sampling framework by Feldman and Langberg [21, 22]. Our results can be extended to polylines of constant complexity with a runningtime of O(n + ε−O(k)).

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © Sergio Cabello and Panos Giannopoulos; licensed under Creative Commons License CC-BY 4.0.
Publisher Keywords: s k-means clustering, segments, polylines, Hausdorff distance, Fréchet mean
Subjects: Q Science > QA Mathematics
Departments: School of Science & Technology > Computer Science > giCentre
[thumbnail of LIPIcs-ESA-2023-28.pdf]
Preview
Text - Published Version
Available under License Creative Commons: Attribution International Public License 4.0.

Download (784kB) | Preview

Export

Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login