Document Open Access Logo

Best Laid Plans of Lions and Men

Authors Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.6.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Mikkel Abrahamsen
Jacob Holm
Eva Rotenberg
Christian Wulff-Nilsen

Cite As Get BibTex

Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Best Laid Plans of Lions and Men. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.6

Abstract

We answer the following question dating back to J.E. Littlewood (1885-1977): Can two lions catch a man in a bounded area with rectifiable lakes? The lions and the man are all assumed to be points moving with at most unit speed. That the lakes are rectifiable means that their boundaries are finitely long. This requirement is to avoid pathological examples where the man survives forever because any path to the lions is infinitely long. We show that the answer to the question is not always "yes", by giving an example of a region R in the plane where the man has a strategy to survive forever. R is a polygonal region with holes and the exterior and interior boundaries are pairwise disjoint, simple polygons. Our construction is the first truly two-dimensional example where the man can survive.

Next, we consider the following game played on the entire plane instead of a bounded area: There is any finite number of unit speed lions and one fast man who can run with speed 1+epsilon for some value epsilon>0. Can the man always survive? We answer the question in the affirmative for any constant epsilon>0.

Subject Classification

Keywords
  • Lion and man game
  • Pursuit evasion game
  • Winning strategy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Abrahamsen, J. Holm, E. Rotenberg, and C. Wulff-Nilsen. Best laid plans of lions and men. CoRR, abs/1703.03687, 2017. URL: https://arxiv.org/abs/1703.03687.
  2. Martin Aigner and Michael Fromme. A game of cops and robbers. Discrete Applied Mathematics, 8(1):1-12, 1984. Google Scholar
  3. Noga Alon and Abbas Mehrabian. Chasing a fast robber on planar graphs and random graphs. Journal of Graph Theory, 78(2):81-96, 2015. Google Scholar
  4. Alessandro Berarducci and Benedetto Intrigila. On the cop number of a graph. Advances in Applied Mathematics, 14(4):389-403, 1993. Google Scholar
  5. B. Bollobás, I. Leader, and M. Walters. Lion and man - can both win? Israel Journal of Mathematics, 189(1):267-286, 2012. Google Scholar
  6. Béla Bollobás. The Art of Mathematics: Coffee Time in Memphis. Cambridge University Press, 2006. Google Scholar
  7. Béla Bollobás. The lion and the christian, and other pursuit and evasion games. In Dierk Schleicher and Malte Lackmann, editors, An Invitation to Mathematics: From Competitions to Research, pages 181-193. Springer-Verlag Berlin Heidelberg, 2011. Google Scholar
  8. Hallard T. Croft. "Lion and man": A postscript. Journal of the London Mathematical Society, 39:385-390, 1964. Google Scholar
  9. James Flynn. Lion and man: The boundary constraint. SIAM Journal on Control, 11:397-411, 1973. Google Scholar
  10. James Flynn. Lion and man: The general case. SIAM Journal on Control, 12:581-597, 1974. Google Scholar
  11. Robbert Fokkink, Leonhard Geupel, and Kensaku Kikuta. Open problems on search games. In Steve Alpern, Robbert Fokkink, Leszek Antoni Gąsieniec, Roy Lindelauf, and V. S. Subrahmanian, editors, Search Theory: A Game Theoretic Perspective, chapter 5, pages 181-193. Springer-Verlag New York, 2013. Google Scholar
  12. Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, and Karol Suchan. Pursuing a fast robber on a graph. Theoretical Computer Science, 411:1167-1181, 2010. Google Scholar
  13. Vladimir Janković. About a man and lions. Matematički Vesnik, 2:359-361, 1978. Google Scholar
  14. J. Lewin. The lion and man problem revisited. Journal of Optimization Theory and Applications, 49(3):411-430, 1986. Google Scholar
  15. John Edensor Littlewood. Littlewood’s miscellany: edited by Béla Bollobás. Cambridge University Press, 1986. Google Scholar
  16. Peter A. Rado and Richard Rado. More about lions and other animals. Mathematical Sprectrum, 7(3):89-93, 1974/75. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact