Back to Search Start Over

Chasing puppies:Mobile beacon routing on closed curves

Authors :
Buchin, Kevin
de Verdiere, Eric Colin
Abrahamsen, Mikkel
Erickson, Jeff
Kostitsyna, Irina
Löffler, Maarten
Miltzow, Tillmann
Urhausen, Jérôme
Vermeulen, Jordi
Viglietta, Giovanni
Buchin, Kevin
de Verdiere, Eric Colin
Abrahamsen, Mikkel
Erickson, Jeff
Kostitsyna, Irina
Löffler, Maarten
Miltzow, Tillmann
Urhausen, Jérôme
Vermeulen, Jordi
Viglietta, Giovanni
Source :
Abrahamsen , M , Erickson , J , Kostitsyna , I , Löffler , M , Miltzow , T , Urhausen , J , Vermeulen , J & Viglietta , G 2021 , Chasing puppies : Mobile beacon routing on closed curves . in K Buchin & E C de Verdiere (eds) , 37th International Symposium on Computational Geometry, SoCG 2021 . , 5 , Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , Leibniz International Proceedings in Informatics, LIPIcs , vol. 189 , 37th International Symposium on Computational Geometry, SoCG 2021 , Virtual, Buffalo , United States , 07/06/2021 .
Publication Year :
2021

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.

Details

Database :
OAIster
Journal :
Abrahamsen , M , Erickson , J , Kostitsyna , I , Löffler , M , Miltzow , T , Urhausen , J , Vermeulen , J & Viglietta , G 2021 , Chasing puppies : Mobile beacon routing on closed curves . in K Buchin & E C de Verdiere (eds) , 37th International Symposium on Computational Geometry, SoCG 2021 . , 5 , Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , Leibniz International Proceedings in Informatics, LIPIcs , vol. 189 , 37th International Symposium on Computational Geometry, SoCG 2021 , Virtual, Buffalo , United States , 07/06/2021 .
Notes :
application/pdf, English
Publication Type :
Electronic Resource
Accession number :
edsoai.on1322763371
Document Type :
Electronic Resource