City Research Online

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

Export

Downloads