Abstract
Let X be a finite subset of a Euclidean space, and ρ be a real function defined on the pairs of points of X, expressing the “unsimilarity” of points. The problem is to find a partition Pl,…, Pp of X into p 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 ρ, there exists an optimal partition such that the intersection of Pj with the convex hull of Pi 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.