Published in

Elsevier, Theoretical Computer Science

DOI: 10.1016/j.tcs.2015.10.005

Links

Tools

Export citation

Search in Google Scholar

Exact Algorithms for Size Constrained 2-Clustering in the Plane

Journal article published in 2015 by Linda Pini, Jianyi Lin ORCID, Alberto Bertoni, Massimiliano Goldwurm
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Red circle
Postprint: archiving forbidden
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

We study the problem of determining an optimal bipartition {A, B} of a set X of n points in R^2 , under the size constraints |A| = k and |B| = n − k, that minimizes the dispersion of points around their centroid in A and B, both in the case of Euclidean and Manhattan norm. Under the Euclidean norm, we show that the problem can be solved in O(n k^{1/3} log^2 n) time by using known properties on k-sets and convex hulls; moreover, the solutions for all k = 1, 2,. .. , n/2 can be computed O(n^2 log n) time. In the case of Manhattan norm, we present an algorithm for our problem working in O(n^2 log 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) space and rely on separation results of the clusters of optimal solutions of the problem.