Size-constrained 2-clustering in the plane with Manhattan distance.
Alberto Bertoni, Massimiliano Goldwurm, Jianyi Lin, Linda Pini · Italian Conference on Theoretical Computer Science · 2014
We present an algorithm for the 2-clustering problem with cluster size constraints in the plane assuming `1-norm, that works in O(n logn) time and O(n) space. Such a procedure also solves a full version of the problem, computing the optimal solutions for all possible constraints on cluster sizes. The algorithm is based on a separation result concerning the clusters of any optimal solution of the problem and on an extended version of red-black trees to maintain a bipartition of a set of points in the plane.