Best laid plans of lions and men

Mikkel Abrahamsen; Jacob Holm; Eva Rotenberg; Christian Wulff-Nilsen

doi:10.4230/LIPIcs.SoCG.2017.6

Best laid plans of lions and men

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

Department of Computer Science

30 Downloads (Pure)

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 + ϵ for some value ϵ > 0. Can the man always survive? We answer the question in the affirmative for any constant ϵ > 0.

Original language	English
Title of host publication	33rd International Symposium on Computational Geometry (SoCG 2017)
Editors	Boris Aronov, Matthew J. Katz
Number of pages	16
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date	2017
Article number	6
ISBN (Electronic)	978-3-95977-038-5
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2017.6
Publication status	Published - 2017
Event	33rd International Symposium on Computational Geometry - Brisbane, Australia Duration: 4 Jul 2017 → 7 Jul 2017 Conference number: 33

Conference

Conference	33rd International Symposium on Computational Geometry
Number	33
Country/Territory	Australia
City	Brisbane
Period	04/07/2017 → 07/07/2017

Series	Leibniz International Proceedings in Informatics
Volume	77
ISSN	1868-8969

Keywords

Lion and man game
Pursuit evasion game
Winning strategy

Access to Document

10.4230/LIPIcs.SoCG.2017.6Licence: CC BY

Abrahamsen_2017_Best_laid_plansFinal published version, 616 KBLicence: CC BY

Cite this

Best laid plans of lions and men. / Abrahamsen, Mikkel ; Holm, Jacob; Rotenberg, Eva et al.
33rd International Symposium on Computational Geometry (SoCG 2017). ed. / Boris Aronov; Matthew J. Katz. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. 6 (Leibniz International Proceedings in Informatics, Vol. 77).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abrahamsen, M , Holm, J, Rotenberg, E & Wulff-Nilsen, C 2017, Best laid plans of lions and men. in B Aronov & MJ Katz (eds), 33rd International Symposium on Computational Geometry (SoCG 2017)., 6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, vol. 77, 33rd International Symposium on Computational Geometry, Brisbane, Queensland, Australia, 04/07/2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.6

@inproceedings{463cd80bacb3472f86d08157e0cbc0d2,

title = "Best laid plans of lions and men",

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 + ϵ for some value ϵ > 0. Can the man always survive? We answer the question in the affirmative for any constant ϵ > 0.",

keywords = "Lion and man game, Pursuit evasion game, Winning strategy",

author = "Mikkel Abrahamsen and Jacob Holm and Eva Rotenberg and Christian Wulff-Nilsen",

year = "2017",

doi = "10.4230/LIPIcs.SoCG.2017.6",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Boris Aronov and Katz, {Matthew J.}",

booktitle = "33rd International Symposium on Computational Geometry (SoCG 2017)",

note = "33rd International Symposium on Computational Geometry ; Conference date: 04-07-2017 Through 07-07-2017",

}

TY - GEN

T1 - Best laid plans of lions and men

AU - Abrahamsen, Mikkel

AU - Holm, Jacob

AU - Rotenberg, Eva

AU - Wulff-Nilsen, Christian

N1 - Conference code: 33

PY - 2017

Y1 - 2017

N2 - 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 + ϵ for some value ϵ > 0. Can the man always survive? We answer the question in the affirmative for any constant ϵ > 0.

AB - 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 + ϵ for some value ϵ > 0. Can the man always survive? We answer the question in the affirmative for any constant ϵ > 0.

KW - Lion and man game

KW - Pursuit evasion game

KW - Winning strategy

UR - http://www.scopus.com/inward/record.url?scp=85029940351&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2017.6

DO - 10.4230/LIPIcs.SoCG.2017.6

M3 - Article in proceedings

AN - SCOPUS:85029940351

T3 - Leibniz International Proceedings in Informatics

BT - 33rd International Symposium on Computational Geometry (SoCG 2017)

A2 - Aronov, Boris

A2 - Katz, Matthew J.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 33rd International Symposium on Computational Geometry

Y2 - 4 July 2017 through 7 July 2017

ER -

Best laid plans of lions and men

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this