On clustering problems with connected optima in Euclidean spaces

On clustering problems with connected optima in Euclidean spaces

0.00 Avg rating0 Votes
Article ID: iaor19881173
Country: Netherlands
Volume: 43
Start Page Number: 81
End Page Number: 88
Publication Date: May 1989
Journal: Annals of Discrete Mathematics
Authors: ,
Keywords: combinatorial analysis
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 P1,...,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.

Reviews

Required fields are marked *. Your email address will not be published.