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^′⊂S such that |S^′|=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^kn²log²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(k), whenever k<clog²n for some constant c. We then give an exact polynomial-time (O(n⁴k²)) 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²)-time algorithm by Kobayashi et al. (2021). We then present an O(logn)-time 122-approximation algorithm for the problem when k=3 if the points are given in convex position order.