On Clustering to Minimize the Sum of Radii
MetadataShow full item record
Let P be a set of n points in the plane. Consider the problem of finding k disks, each centered at a point in P, whose union covers P with the objective of minimizing the sum of the radii of the disks. We present an exact algorithm for this well-studied problem with polynomial running time, under the assumption that two candidate solutions can be compared efficiently. The algorithm generalizes in a straightforward manner to any fixed dimension and to some other related problems.
A preliminary version of this paper appeared in the 18th ACM-SIAMSymposium on Discrete Algorithms (SODA), San Francisco, CA, 2008, pp. 819–825.