论文标题
连接两个中心问题的接近度有效算法
An Efficient Algorithm for the Proximity Connected Two Center Problem
论文作者
论文摘要
鉴于飞机上的$ n $点的$ p $ $ n $点，$ k $中心的问题是找到$ k $一致的磁盘，最小可能的半径是，使他们的工会在$ p $中涵盖了所有点。 $ 2 $ - 中心问题是$ k $ - 中心问题的一种特殊情况，在最近的过去\ cite {cahn，ht，sh}中已经进行了广泛的研究。在本文中，我们考虑了$ 2 $ - 中心问题的广义版本，称为\ textit {proximity connected} $ 2 $ - center（pctc）问题。在此问题中，我们还为我们提供了一个参数$δ\ geq 0 $，并且我们有一个额外的约束，即磁盘中心之间的距离最多应为$δ$。请注意，当$δ= 0 $时，PCTC问题将减少到$ 1 $ - center（最小封闭磁盘）问题，当$δ$倾向于无穷大时，将其减少到$ 2 $ center的问题。 PCTC问题首先出现在1992年的无线网络的背景下\ cite {acn0}，但获得了该问题的非平凡确定性算法。在本文中，我们通过为问题提供确定性$ O（n^2 \ log n）$ time算法来解决这个开放问题。
Given a set $P$ of $n$ points in the plane, the $k$-center problem is to find $k$ congruent disks of minimum possible radius such that their union covers all the points in $P$. The $2$-center problem is a special case of the $k$-center problem that has been extensively studied in the recent past \cite{CAHN,HT,SH}. In this paper, we consider a generalized version of the $2$-center problem called \textit{proximity connected} $2$-center (PCTC) problem. In this problem, we are also given a parameter $δ\geq 0$ and we have the additional constraint that the distance between the centers of the disks should be at most $δ$. Note that when $δ=0$, the PCTC problem is reduced to the $1$-center(minimum enclosing disk) problem and when $δ$ tends to infinity, it is reduced to the $2$-center problem. The PCTC problem first appeared in the context of wireless networks in 1992 \cite{ACN0}, but obtaining a nontrivial deterministic algorithm for the problem remained open. In this paper, we resolve this open problem by providing a deterministic $O(n^2\log n)$ time algorithm for the problem.
