2026-07-24T18:11:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13804 2024-03-06T10:52:45Z ddc:004 open_access

Chasing Puppies: Mobile Beacon Routing on Closed Curves Abrahamsen, Mikkel Erickson, Jeff Kostitsyna, Irina Löffler, Maarten Miltzow, Tillmann Urhausen, Jérôme Vermeulen, Jordi Viglietta, Giovanni Beacon routing navigation generic smooth curves puppies We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others’ work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikkel Abrahamsen and Jeff Erickson and Irina Kostitsyna and Maarten Löffler and Tillmann Miltzow and Jérôme Urhausen and Jordi Vermeulen and Giovanni Viglietta 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.5 urn:nbn:de:0030-drops-138046 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.5 eng https://creativecommons.org/licenses/by/4.0/legalcode