For a set 𝒟 of disks in the plane, its disk graph G (𝒟) is the graph with vertex set 𝒟, where two vertices are adjacent if and only if the corresponding disks intersect. Given a set 𝒟 of n weighted disks, computing a maximum independent set of G (𝒟) is NP-hard. In this paper, we present an O (n³log n) -time algorithm for this problem in a special setting in which the disks are in convex position, meaning that every disk appears on the convex hull of 𝒟. This setting has been studied previously for disks of equal radius, for which an O (n^37/11) -time algorithm was known. Our algorithm also works in the weighted case where disks have weights and the goal is to compute a maximum-weight independent set. As an application of our result, we obtain an O (n³log² n) -time algorithm for the dispersion problem on a set of n disks in convex position: given an integer k, compute a subset of k disks that maximizes the minimum pairwise distance among all disks in the subset.
Tkachenko et al. (Thu,) studied this question.