In the original version of the lion and man game, a lion tries to capture a man who is trying to escape in a circular arena. The players have equal speeds. They can observe each other at all times. We study a new variant of the game in which the lion has only line-of-sight visibility. That is it can observe the man’s position only if the line segment connecting them does not intersect the boundary. We show that despite this limitation, the lion can capture the man in any monotone polygon in finite time.
AlonsoLGoldsteinASReingoldEM (1992) Lion and man: Upper and lower bounds. INFORMS Journal on Computing4(4): 447.
2.
BhadauriaDIslerV (2011) Capturing an evader in a polygonal environment with obstacles. In: Proceedings of International Joint Conference on Artificial Intelligence.
3.
ChungTHollingerGIslerV (2011) Search and pursuit–evasion in mobile robotics. Autonomous Robots31(4): 299–316.
4.
De BergMCheongOvan KreveldM (2008) Computational Geometry: Algorithms and Applications. Berlin: Springer.
5.
GuibasLJHershbergerJLevenDSharirMTarjanR (1987) Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica2: 209–233.
6.
GuibasLJLatombeJCLavalleSMLinDMotwaniR (1999) A visibility-based pursuit–evasion problem. International Journal of Computational Geometry and Applications9(4–5): 471–493. DOI: 10.1142/S0218195999000273.
IslerVKannanSKhannaS (2005) Randomized pursuit–evasion in a polygonal environment. IEEE Transactions on Robotics21(5): 875–884.
9.
KleinKSuriS (2011) Complete information pursuit evasion in polygonal environments. In: Proceedings of the 25th Conference on Artificial Intelligence (AAAI), pp. 1120–1125.
10.
LittlewoodJE (1953) A Mathematician’s Miscellany. London: Methuen.
11.
SgallJ (2001) Solution of David Gale’s lion and man problem. Theoretical Computer Science259: 663–670.
12.
SuzukiIYamashitaM (1992) Searching for a mobile intruder in a polygonal region. SIAM Journal on Computing21(5): 863–888. DOI: 10.1137/0221051.
13.
TovarBLaValleSM (2008) Visibility-based pursuit–evasion with bounded speed. The International Journal of Robotics Research27(11–12): 1350–1360.