Chasing Puppies: Mobile Beacon Routing on Closed Curves

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 4,06 MB, PDF-dokument

  • 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 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.

OriginalsprogEngelsk
TidsskriftJournal of Computational Geometry
Vol/bind13
Udgave nummer2
Sider (fra-til)115-150
ISSN1920-180X
DOI
StatusUdgivet - 2022
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

Bibliografisk note

Funding Information:
M.A. partially supported by the VILLUM Foundation grant 16582. M.L. partially supported by the Dutch Research Council (NWO) under project number 614.001.504 and 628.011.005. T.M. supported by the Dutch Research Council (NWO) under Veni grant 016.Veni.192.250. J.U. supported by the Dutch Research Council (NWO) under project number 612.001.651. J.V. supported by the Dutch Research Council (NWO) under project number 612.001.651.

Publisher Copyright:
© 2022, Carleton University. All rights reserved.

ID: 344803409