An alternative proof for the equivalence of infinity-searcher and 2-searcher

作者：Kameda Tsunehiko; Suzuki Ichiro^*; Yamashita Masafumi

来源：Theoretical Computer Science, 2016, 634: 108-119.

DOI：10.1016/j.tcs.2016.04.016

• Polygon search
• 2-Searcher
• infinity-Searcher
• Equivalence

It was conjectured in 1992 that the 2-searcher, who has two flashlights, has the same searching capability as the infinity-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 the 2-link visibility diagram that represents 2-link visibility, which has other applications.

• 出版日期2016-6-27