Chasing Puppies

Chasing Puppies: Mobile Beacon Routing on Closed Curves

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

Chasing Puppies : Mobile Beacon Routing on Closed Curves. / Abrahamsen, Mikkel; Erickson, Jeff; Kostitsyna, Irina; Löffler, Maarten; Miltzow, Tillmann; Urhausen, Jérôme; Vermeulen, Jordi; Viglietta, Giovanni.

I: Journal of Computational Geometry, Bind 13, Nr. 2, 2022, s. 115-150.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Abrahamsen, M, Erickson, J, Kostitsyna, I, Löffler, M, Miltzow, T, Urhausen, J, Vermeulen, J & Viglietta, G 2022, 'Chasing Puppies: Mobile Beacon Routing on Closed Curves', Journal of Computational Geometry, bind 13, nr. 2, s. 115-150. https://doi.org/10.20382/jocg.v13i2a7

APA

Abrahamsen, M., Erickson, J., Kostitsyna, I., Löffler, M., Miltzow, T., Urhausen, J., Vermeulen, J., & Viglietta, G. (2022). Chasing Puppies: Mobile Beacon Routing on Closed Curves. Journal of Computational Geometry, 13(2), 115-150. https://doi.org/10.20382/jocg.v13i2a7

Vancouver

Abrahamsen M, Erickson J, Kostitsyna I, Löffler M, Miltzow T, Urhausen J o.a. Chasing Puppies: Mobile Beacon Routing on Closed Curves. Journal of Computational Geometry. 2022;13(2):115-150. https://doi.org/10.20382/jocg.v13i2a7

Author

Abrahamsen, Mikkel ; Erickson, Jeff ; Kostitsyna, Irina ; Löffler, Maarten ; Miltzow, Tillmann ; Urhausen, Jérôme ; Vermeulen, Jordi ; Viglietta, Giovanni. / Chasing Puppies : Mobile Beacon Routing on Closed Curves. I: Journal of Computational Geometry. 2022 ; Bind 13, Nr. 2. s. 115-150.

Bibtex

@article{a16c1a6dfc924e58942c49f3a378eb0e,

title = "Chasing Puppies: Mobile Beacon Routing on Closed Curves",

abstract = "We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others{\textquoteright} 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{\textquoteright}s speed is unbounded.",

author = "Mikkel Abrahamsen and Jeff Erickson and Irina Kostitsyna and Maarten L{\"o}ffler and Tillmann Miltzow and J{\'e}r{\^o}me Urhausen and Jordi Vermeulen and Giovanni Viglietta",

note = "Publisher Copyright: {\textcopyright} 2022, Carleton University. All rights reserved.; 37th International Symposium on Computational Geometry, SoCG 2021 ; Conference date: 07-06-2021 Through 11-06-2021",

year = "2022",

doi = "10.20382/jocg.v13i2a7",

language = "English",

volume = "13",

pages = "115--150",

journal = "Journal of Computational Geometry",

issn = "1920-180X",

publisher = "Computational Geometry Laboratory",

number = "2",

}

RIS

TY - JOUR

T1 - Chasing Puppies

T2 - 37th International Symposium on Computational Geometry, SoCG 2021

AU - Abrahamsen, Mikkel

AU - Erickson, Jeff

AU - Kostitsyna, Irina

AU - Löffler, Maarten

AU - Miltzow, Tillmann

AU - Urhausen, Jérôme

AU - Vermeulen, Jordi

AU - Viglietta, Giovanni

PY - 2022

Y1 - 2022

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

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

U2 - 10.20382/jocg.v13i2a7

DO - 10.20382/jocg.v13i2a7

M3 - Journal article

AN - SCOPUS:85146516871

VL - 13

SP - 115

EP - 150

JO - Journal of Computational Geometry

JF - Journal of Computational Geometry

SN - 1920-180X

IS - 2

Y2 - 7 June 2021 through 11 June 2021

ER -

ID: 344803409

Datalogisk Institut