Randomized Algorithms for Variance-Based $k$-Clustering
Mary Inaba, Naoki Katoh, Hiroshi Imai · Kyoto University Research Information Repository (Kyoto University) · 1994
In this paper we consider the k-clustering problem for a set $S$ of $n$ points in the d-dimensional space with minsum sum of squared errors as clustering criteria, which is motivated from a problem, called color quantization problem, of computing a color lookup table for frame buffer display.Using the technique of computational geometry and random sampling, we present an efficient randomized algorithm which, roughly speaking, finds an $\epsilon$ -approximate 2-clustering in $O(n(1/\epsilon)^{d})$ time.