An alternative proof for the equivalence of ∞-searcher and 2-searcher
An alternative proof for the equivalence of ∞-searcher and 2-searcher
复制标题
∞-搜索器和 2-搜索器等价性的另一种证明
DOI：
10.1016/j.tcs.2016.04.016
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
and Masafumi Yamashita
中科院分区：
文献类型：
--
作者：
Tsunehiko Kameda;Ichiro Suzuki;and Masafumi Yamashita
1992年有人推测，拥有两个手电筒的2-Search具有与拥有全向光源的∞-Search相同的搜索能力。Park等人。2001年肯定地证明了这一猜想，但他们的证明相当复杂，不容易理解。在这篇文章中，我们提出了另一种证明，我们认为它在概念上更透明，更容易理解。为此，我们引入了一个称为2-link可见性图的工具，它代表了2-link可见性，它还有其他的应用。
It was conjectured in 1992 that the 2-searcher, who has two flashlights, has the same searching capability as the ∞-searcher, who has an omni-directional light source. Park et al. proved this conjecture affirmatively in 2001, but their proof is rather complicated and not easy to understand. In this paper we present an alternative proof, which we believe is conceptually more transparent and easier to understand. For this purpose, we introduce a tool called the2-link visibility diagramthat represents 2-link visibility, which has other applications.