论文标题
Max-min $ k $ - 凸多边形的分散
Max-Min $k$-Dispersion on a Convex Polygon
论文作者
论文摘要
在本文中，我们考虑以下$ K $分散问题。鉴于$ n $ s $ n $点位于飞机上的位置，而整数$ k $（$ 0 <k <n $），目标是计算一个子集$ s'\ subset s $，以便最大化$ | s'| = k $ and $ s之间的最小距离。基于有限的搜索树方法，我们在$ o（2^k（n^2 \ log n+n+n（\ log^2 n）（\ log k）（\ log k）））$ time中提出了一种精确的固定参数算法，其中$ k $是参数。所提出的精确算法比当前最佳精确指数算法[$ n^{o（\ sqrt {k}）} $ - akagi et al。，（2018）的时间算法，每当$ k <c \ log log^c \ log^2 {n} $ for Soments nounds fors nose nostand $ c $时。然后，我们提出一个$ o（\ log {n}）$ - 时间$ \ frac {1} {2 \ sqrt {2}} $ - 当$ k = 3 $以cONVEX位置顺序给出点时，该问题的近似算法。
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'\subset 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^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.
