Optimal Separable Partitioning in the Plane

Sets of points are called separable if their convex hulls are disjoint. We suggest a technique for optimally partitioning of a set N into two separable subsets, N 1 ; N 2 . We assume that a monotone measure, ¯, is defined over the subsets of N , and the objective is to minimize maxf¯(N 1 ); ¯(N 2 )g. 1 Introduction Let V = fv 1 ; v 2 ; : : : ; v n g be a set of n points in the plane. The problem of partitioning V into clusters has a wide range of applications and exact and heuristic algorithms have been developed to solve such problems. A partition (V 0 ; ¯ V 0 ) of V is called separable if the convex hulls of V 0 and ¯ V 0 are disjoint. In this paper we suggest a new approach for computing optimal separable partitions with respect to a class of objective functions of the min-max type. The basic idea of our approach relies on the possibility, under certain conditions, to apply binary search in order to select the best separable partition from a sequence of nested separable..