TY - JOUR
T1 - An alternative proof for the equivalence of ∞-searcher and 2-searcher
AU - Kameda, Tsunehiko
AU - Suzuki, Ichiro
AU - Yamashita, Masafumi
N1 - Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2016/6/27
Y1 - 2016/6/27
N2 - 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 the 2-link visibility diagram that represents 2-link visibility, which has other applications.
AB - 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 the 2-link visibility diagram that represents 2-link visibility, which has other applications.
UR - http://www.scopus.com/inward/record.url?scp=84963831172&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84963831172&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2016.04.016
DO - 10.1016/j.tcs.2016.04.016
M3 - Article
AN - SCOPUS:84963831172
SN - 0304-3975
VL - 634
SP - 108
EP - 119
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -