Chasing puppies: Mobile beacon routing on closed curves

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

doi:10.4230/LIPIcs.SoCG.2021.5

Chasing puppies: Mobile beacon routing on closed curves

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	37th International Symposium on Computational Geometry, SoCG 2021
Editors	Kevin Buchin, Eric Colin de Verdiere
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)	9783959771849
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2021.5
Publication status	Published - 1 Jun 2021
Event	37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States Duration: 7 Jun 2021 → 11 Jun 2021

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	189
ISSN (Print)	1868-8969

Conference

Conference	37th International Symposium on Computational Geometry, SoCG 2021
Country/Territory	United States
City	Virtual, Buffalo
Period	7/06/21 → 11/06/21

Bibliographical note

Funding Information:
Funding Mikkel Abrahamsen: Partially supported by the VILLUM Foundation grant 16582. Maarten Löffler: Partially supported by the Dutch Research Council (NWO) under project number 614.001.504 and 628.011.005. Tillmann Miltzow: Supported by the Dutch Research Council (NWO) under Veni grant EAGER. Jérôme Urhausen: Supported by the Dutch Research Council (NWO); 612.001.651. Jordi Vermeulen: Supported by the Dutch Research Council (NWO); 612.001.651.

Publisher Copyright:
© Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).

Keywords

Beacon routing
Generic smooth curves
Navigation
Puppies

Access to Document

10.4230/LIPIcs.SoCG.2021.5

Cite this

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 Article 5 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 189). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.5

@inproceedings{1e973eae57c6441aa6359ec5d001ad18,

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' 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.",

keywords = "Beacon routing, Generic smooth curves, Navigation, Puppies",

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 = "Funding Information: Funding Mikkel Abrahamsen: Partially supported by the VILLUM Foundation grant 16582. Maarten L{\"o}ffler: Partially supported by the Dutch Research Council (NWO) under project number 614.001.504 and 628.011.005. Tillmann Miltzow: Supported by the Dutch Research Council (NWO) under Veni grant EAGER. J{\'e}r{\^o}me Urhausen: Supported by the Dutch Research Council (NWO); 612.001.651. Jordi Vermeulen: Supported by the Dutch Research Council (NWO); 612.001.651. Publisher Copyright: {\textcopyright} Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten L{\"o}ffler, Tillmann Miltzow, J{\'e}r{\^o}me Urhausen, Jordi Vermeulen, and Giovanni Viglietta; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).; 37th International Symposium on Computational Geometry, SoCG 2021 ; Conference date: 07-06-2021 Through 11-06-2021",

year = "2021",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2021.5",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Kevin Buchin and {de Verdiere}, {Eric Colin}",

booktitle = "37th International Symposium on Computational Geometry, SoCG 2021",

}

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 & EC de Verdiere (eds), 37th International Symposium on Computational Geometry, SoCG 2021., 5, Leibniz International Proceedings in Informatics, LIPIcs, vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 37th International Symposium on Computational Geometry, SoCG 2021, Virtual, Buffalo, United States, 7/06/21. https://doi.org/10.4230/LIPIcs.SoCG.2021.5

Chasing puppies: Mobile beacon routing on closed curves. / Abrahamsen, Mikkel; Erickson, Jeff; Kostitsyna, Irina et al.
37th International Symposium on Computational Geometry, SoCG 2021. ed. / Kevin Buchin; Eric Colin de Verdiere. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. 5 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 189).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

N1 - Funding Information: Funding Mikkel Abrahamsen: Partially supported by the VILLUM Foundation grant 16582. Maarten Löffler: Partially supported by the Dutch Research Council (NWO) under project number 614.001.504 and 628.011.005. Tillmann Miltzow: Supported by the Dutch Research Council (NWO) under Veni grant EAGER. Jérôme Urhausen: Supported by the Dutch Research Council (NWO); 612.001.651. Jordi Vermeulen: Supported by the Dutch Research Council (NWO); 612.001.651. Publisher Copyright: © Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).

PY - 2021/6/1

Y1 - 2021/6/1

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

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

KW - Beacon routing

KW - Generic smooth curves

KW - Navigation

KW - Puppies

UR - http://www.scopus.com/inward/record.url?scp=85108211822&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2021.5

DO - 10.4230/LIPIcs.SoCG.2021.5

M3 - Conference contribution

AN - SCOPUS:85108211822

T3 - Leibniz International Proceedings in Informatics, LIPIcs

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

A2 - Buchin, Kevin

A2 - de Verdiere, Eric Colin

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Y2 - 7 June 2021 through 11 June 2021

ER -

Abrahamsen M, Erickson J, Kostitsyna I, Löffler M, Miltzow T, Urhausen J et al. Chasing puppies: Mobile beacon routing on closed curves. In Buchin K, de Verdiere EC, editors, 37th International Symposium on Computational Geometry, SoCG 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2021. 5. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.SoCG.2021.5

Chasing puppies: Mobile beacon routing on closed curves

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this