About

Log in?

DTU users get better search results including licensed content and discounts on order fees.

Anyone can log in and get personalized features such as favorites, tags and feeds.

Log in as DTU user Log in as non-DTU user No thanks

DTU Findit

Conference paper

Best laid plans of lions and men

From

University of Copenhagen1

Department of Applied Mathematics and Computer Science, Technical University of Denmark2

Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark3

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.

Language: English
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Year: 2017
Pages: 61-616
Proceedings: 33rd International Symposium on Computational Geometry, SoCG 2017Symposium on Computational Geometry
Series: Leibniz International Proceedings in Informatics
ISBN: 3959770383 and 9783959770385
ISSN: 18688969
Types: Conference paper
DOI: 10.4230/LIPIcs.SoCG.2017.6
ORCIDs: Rotenberg, Eva , 0000-0003-2734-4690 , 0000-0001-6997-9251 and 0000-0002-3699-7821

DTU users get better search results including licensed content and discounts on order fees.

Log in as DTU user

Access

Analysis