On clustering problems with connected optima in euclidean spaces

Endre Boros, Peter L. Hammer

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)81-88
Number of pages8
JournalDiscrete Mathematics
Issue number1-3
StatePublished - May 1989

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On clustering problems with connected optima in euclidean spaces'. Together they form a unique fingerprint.

Cite this