Chasing puppies: Mobile beacon routing on closed curves
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Chasing Puppies
Final published version, 3.08 MB, PDF document
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 language | English |
---|---|
Title of host publication | 37th International Symposium on Computational Geometry, SoCG 2021 |
Editors | Kevin Buchin, Eric Colin de Verdiere |
Number of pages | 19 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2021 |
Article number | 5 |
ISBN (Electronic) | 9783959771849 |
DOIs | |
Publication status | Published - 2021 |
Event | 37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States Duration: 7 Jun 2021 → 11 Jun 2021 |
Conference
Conference | 37th International Symposium on Computational Geometry, SoCG 2021 |
---|---|
Land | United States |
By | Virtual, Buffalo |
Periode | 07/06/2021 → 11/06/2021 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 189 |
ISSN | 1868-8969 |
- Beacon routing, Generic smooth curves, Navigation, Puppies
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
ID: 273638336