Clustering is a very important problem in statistics, image understanding, computer graphics, etc. There are two
types of clustering problem, one is clustering on a weighted graph (or a (dis)similarity matrix), and the other is
a geometric one. Geometric clustering has nicer structures than the graph version due to constraints induced by
geometry. This paper first summarizes recent results by the authors on the k-clustering problem for a set S of n
points p i = (x i ) (i = 1; . . . ; n) in the d-dimensional space with variance-based errors as clustering criteria. A main
problem is to find a k-clustering of S into S j (j = 1; . . . ; k) minimizing
k
X
j=1
X
p i 2S j
kx i 0 ¯
x(S j )k 2
where k 1 k is the L 2 norm and ¯
x(S j ) is the centroid of points in S j , i.e., 1
jS j j
P
p i
2S j
x i . Next, relations of those
results with the existing local improvement technique, called k-means, are described, together with results of compu-
tational experiments. Furthermore, connections of this geometric clustering problem with the so-called geographical
optimization problem proposed by Iri, Murota and Ohya [3] are mentioned.