Best laid plans of lions and men
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Best laid plans of lions and men. / Abrahamsen, Mikkel; Holm, Jacob; Rotenberg, Eva; Wulff-Nilsen, Christian.
33rd International Symposium on Computational Geometry (SoCG 2017). red. / Boris Aronov; Matthew J. Katz. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. 6 (Leibniz International Proceedings in Informatics, Bind 77).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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
Y2 - 4 July 2017 through 7 July 2017
ER -
ID: 188448934