## 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 P_{1},...,P_{p} 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 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.

Original language | English (US) |
---|---|

Pages (from-to) | 81-88 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 75 |

Issue number | 1-3 |

DOIs | |

State | Published - May 1989 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics