Efficient Algorithms for Variance-Based k-Clustering.
Sumiko Hasegawa, Hideyuki Imai, Minoru Inaba, Junji Nakano, Naoki Katoh · 1993
In this paper we consider the k-clustering problem for n points in the d-dimensional space, motivated from the problem of computing a color lookup table for frame buffer display, and that of compressing two-dimensional image data. Using the technique of computational geometry, this clustering problem is investigated in a unified manner. 1 Introduction Clustering is the grouping of similar objects and a clustering of a set is a partition of its elements that is chosen to minimize some measure of dissimilarity [11, 19]. It is very fundamental and used in various fields in computer science such as patern recognition, learning theory, and color quantization in computer graphics. There are various kinds of measure of dissimilarity, called criteria, in compliance with the problem. In this paper we investigate the clustering problem suited for the color quantization problem. In general, intensity of the three primary colors RGB (red, green, blue) are used to control digital graphical device...