Chasing puppies: Mobile beacon routing on closed curves

Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, Giovanni Viglietta

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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.

Original languageEnglish
Title of host publication37th International Symposium on Computational Geometry, SoCG 2021
EditorsKevin Buchin, Eric Colin de Verdiere
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959771849
DOIs
Publication statusPublished - 1 Jun 2021
Event37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States
Duration: 7 Jun 202111 Jun 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume189
ISSN (Print)1868-8969

Conference

Conference37th International Symposium on Computational Geometry, SoCG 2021
Country/TerritoryUnited States
CityVirtual, Buffalo
Period7/06/2111/06/21

Bibliographical note

Funding Information:
Funding Mikkel Abrahamsen: Partially supported by the VILLUM Foundation grant 16582. Maarten Löffler: Partially supported by the Dutch Research Council (NWO) under project number 614.001.504 and 628.011.005. Tillmann Miltzow: Supported by the Dutch Research Council (NWO) under Veni grant EAGER. Jérôme Urhausen: Supported by the Dutch Research Council (NWO); 612.001.651. Jordi Vermeulen: Supported by the Dutch Research Council (NWO); 612.001.651.

Publisher Copyright:
© Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).

Keywords

  • Beacon routing
  • Generic smooth curves
  • Navigation
  • Puppies

Cite this