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


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]
Text - Accepted Version
Available under License Creative Commons: Attribution International Public License 4.0.

Download (784kB) | Preview


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


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login