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. doi: 10.48550/arXiv.2305.10922


We study the problem of k-means clustering in the space of straight-line segments in R2 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~\cite{Vigneron14} 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~\cite{Feldman11, Feldman2020}. Our results can be extended to polylines of constant complexity with a running time of O(n+ϵ−O(k)).

Publication Type: Other (Preprint)
Publisher Keywords: k-means clustering, segments, polylines, Hausdorff distance, Fréchet mean
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science > giCentre


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