Best laid plans of lions and men

Research output: Research - peer-reviewArticle in proceedings – Annual report year: 2017

View graph of relations

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 languageEnglish
Title of host publication33rd International Symposium on Computational Geometry, SoCG 2017
Number of pages556
Volume77
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1 Jun 2017
Pages61-616
ISBN (Electronic)9783959770385
DOIs
StatePublished - 1 Jun 2017
Event33rd International Symposium on Computational Geometry, SoCG 2017 - Brisbane, Australia
Duration: 4 Jul 20177 Jul 2017

Conference

Conference33rd International Symposium on Computational Geometry, SoCG 2017
CountryAustralia
CityBrisbane
Period04/07/201707/07/2017
SponsorUniversity of Queensland
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

  • Lion and man game, Pursuit evasion game, Winning strategy
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 140495666