Exact algorithms for 2-clustering with size constraints in the Euclidean plane

We study the problem of determining an optimal bipartition {A,B} of a set X of n points in ℝ^2 that minimizes the sum of the sample variances of A and B, under the size constraints |A| = k and |B| = n − k. We present two algorithms for such a problem. The first one computes the solution in O(n\sqrt[3]{k}\log^2 n) time by using known results on convex-hulls and k-sets. The second algorithm, for an input X ⊂ ℝ^2 of size n, solves the problem for all k = 1,2,..., n/2 and works in O(n^2 logn) time.