Chasing puppies: Mobile beacon routing on closed curves

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

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

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.

OriginalsprogEngelsk
Titel37th International Symposium on Computational Geometry, SoCG 2021
RedaktørerKevin Buchin, Eric Colin de Verdiere
Antal sider19
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato2021
Artikelnummer5
ISBN (Elektronisk)9783959771849
DOI
StatusUdgivet - 2021
Begivenhed37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, USA
Varighed: 7 jun. 202111 jun. 2021

Konference

Konference37th International Symposium on Computational Geometry, SoCG 2021
LandUSA
ByVirtual, Buffalo
Periode07/06/202111/06/2021
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind189
ISSN1868-8969

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 273638336