On clustering problems with connected optima in Euclidean spaces (Q1116236)

Let X be a finite subset of a Euclidean space, and \(\rho\) be a real function defined on the pairs of points of X, expressing the ``unsimilarity'' of points. The problem is to find a partition \(P_ 1,....,P_ p\) of X into \(\rho\) groups which maximizes the sum of unsimilarities of all those pairs of points which do not belong to the same group. It is shown here that for some typical unsimilarities \(\rho\), there exists an optimal partition such that the intersection of \(P_ j\) with the convex hull of \(P_ i\) is empty for all \(i<j\). In particular, it is shown that if X is on a sphere then the convex hulls of the groups of an optimal partition are pairwise disjoint.