License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.5
URN: urn:nbn:de:0030-drops-138046
Go to the corresponding LIPIcs Volume Portal

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

Chasing Puppies: Mobile Beacon Routing on Closed Curves

LIPIcs-SoCG-2021-5.pdf (3 MB)


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.

BibTeX - Entry

  author =	{Abrahamsen, Mikkel and Erickson, Jeff and Kostitsyna, Irina and L\"{o}ffler, Maarten and Miltzow, Tillmann and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi and Viglietta, Giovanni},
  title =	{{Chasing Puppies: Mobile Beacon Routing on Closed Curves}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-138046},
  doi =		{10.4230/LIPIcs.SoCG.2021.5},
  annote =	{Keywords: Beacon routing, navigation, generic smooth curves, puppies}

Keywords: Beacon routing, navigation, generic smooth curves, puppies
Collection: 37th International Symposium on Computational Geometry (SoCG 2021)
Issue Date: 2021
Date of publication: 02.06.2021
Supplementary Material: Software (Source Code): archived at:

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI