Max-Min $k$-Dispersion on a Convex Polygon

Abstract

In this paper, we consider the following $k$-dispersion problem. Given a set $S$ of $n$ points placed in the plane in a convex position, and an integer $k$ ($0<k<n$), the objective is to compute a subset $S^{\prime }\subset S$ such that $|S^{\prime }|=k$ and the minimum distance between a pair of points in $S^{\prime }$ is maximized. Based on the bounded search tree method we propose an exact fixed-parameter algorithm in $O(2^k(n^2\log n+n({\log }^{2}n)(\log k)))$ time, for this problem, where $k$ is the parameter. The proposed exact algorithm is better than the current best exact exponential algorithm [$n^{O(\sqrt{k})}$-time algorithm by Akagi et al.,(2018)] whenever $k<c{\log }^{2}n$ for some constant $c$. We then present an $O(\log n)$-time $\frac{1}{2\sqrt{2}}$-approximation algorithm for the problem when $k=3$ if the points are given in convex position order.

10 pages, 5 figures