Exact algorithms for size constrained 2-clustering in the plane

We study the problem of determining an optimal bipartition {A,B}{A,B} of a set X of n   points in R2R2, under the size constraints |A|=k|A|=k and |B|=n−k|B|=n−k, that minimizes the dispersion of points around their centroid in A and B  , both in the cases of Euclidean and Manhattan norms. Under the Euclidean norm, we show that the problem can be solved in O(nk3log2⁡n) time by using known properties on k  -sets and convex hulls; moreover, the solutions for all k=1,2,…,⌊n/2⌋k=1,2,…,⌊n/2⌋ can be computed in O(n2log⁡n)O(n2log⁡n) time. In the case of Manhattan norm, we present an algorithm working in O(n2log⁡n)O(n2log⁡n) time, which uses an extended version of red–black trees to maintain a bipartition of a planar point set. Also in this case we provide a full version of the algorithm yielding the solutions for all size constraints k  . All these procedures work in O(n)O(n) space and rely on separation results of the clusters of optimal solutions.