Chasing puppies: Mobile beacon routing on closed curves

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

🔥Proceedings of the 37th International Symposium on Computational Geometry, 5:1--5:19, 2021.


We solve an open problem posed by Micheal Biro in 2013, motivated by his and other's 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 well-behaved, we prove that the human can always catch the puppy in finite time.

Publications - Jeff Erickson ( 12 Feb 2021