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: Contribution to journalArticlepeer-review


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 along the curve (faster than the human) always reducing the Euclidean straight-line distance to the human, and stopping only when 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. Our results hold regardless of the relative speeds of puppy and human, and even if the puppy’s speed is unbounded.

Original languageEnglish (US)
Pages (from-to)115-150
Number of pages36
JournalJournal of Computational Geometry
Issue number2
StatePublished - 2022

ASJC Scopus subject areas

  • Geometry and Topology
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Chasing Puppies: Mobile Beacon Routing on Closed Curves'. Together they form a unique fingerprint.

Cite this