Algorithms for k-Dispersion for Points in Convex Position in the Plane

In this paper, we consider the following k-dispersion problem. Given a set S of n points placed in the plane in convex position and an integer k (0 < k < n), the objective is to compute a subset S' subset of S such that vertical bar S'vertical bar = k and the minimum distance between a pair of points in S' is maximized. Based on the bounded search tree method, we propose an exact fixed-parameter algorithm in O(2(k)n(2) log(2) n) time for this problem, where k is the parameter. The proposed exact algorithm improves on the algorithm of Akagi et al. (2018), which requires time n(O)(root k), whenever k < c log(2) n for some constant c. We then give an exact polynomial-time (O(n4k2)) algorithm, for any k > 0, thus answering the open question about the complexity of this restricted dispersion problem. For k = 3, there is an O(n(2))-time algorithm by Kobayashi et al. (2021).