Maximum Centre-Disjoint Mergeable Disks
This work addresses a theoretical problem in computational geometry with applications to map labeling, but the NP-hardness result is incremental given similar problems are known to be hard.
The paper proves that the problem of selecting a maximum subset of disks such that no disk contains the center of another, with remaining disks merged into selected ones, is NP-hard. It provides an ILP formulation and a polynomial-time algorithm for the special case where disk centers lie on a line.
Given a set of disks in the plane, the goal of the problem studied in this paper is to choose a subset of these disks such that none of its members contains the centre of any other. Each disk not in this subset must be merged with one of its nearby disks that is, increasing the latter's radius. This problem has applications in labelling rotating maps and in visualizing the distribution of entities in static maps. We prove that this problem is NP-hard. We also present an ILP formulation for this problem, and a polynomial-time algorithm for the special case in which the centres of all disks are on a line.