City Research Online

Abstract

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

Export

Downloads