Document Open Access Logo

Chasing Puppies: Mobile Beacon Routing on Closed Curves

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.5.pdf
  • Filesize: 3.08 MB
  • 19 pages

Document Identifiers

Author Details

Mikkel Abrahamsen
  • BARC, University of Copenhagen, Denmark
Jeff Erickson
  • University of Illinois at Urbana-Champaign, IL, USA
Irina Kostitsyna
  • Eindhoven University of Technology, The Netherlands
Maarten Löffler
  • Utrecht University, The Netherlands
Tillmann Miltzow
  • Utrecht University, The Netherlands
Jérôme Urhausen
  • Utrecht University, The Netherlands
Jordi Vermeulen
  • Utrecht University, The Netherlands
Giovanni Viglietta
  • Japan Advanced Institute of Science and Technology, Nomi City, Ishikawa, Japan

Funding

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

Acknowledgements

The authors wish to thank the anonymous reviewers for useful comments and suggestions. Thanks to Ivor van der Hoog, Marc van Kreveld, and Frank Staals for helpful discussions in the early stages of this work, and to Joseph O'Rourke for clarifying the history of the problem. Portions of this work were done while the second author was visiting Utrecht University.

Cite AsGet BibTex

Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.5

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Beacon routing
  • navigation
  • generic smooth curves
  • puppies

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Zachary Abel, Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jason S. Ku, and Jayson Lynch. Negative instance for the edge patrolling beacon problem. Preprint, 2020. URL: http://arxiv.org/abs/2006.01202.
  2. Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta. Chasing puppies: Mobile beacon routing on closed curves, 2021. URL: http://arxiv.org/abs/2103.09811.
  3. Israel Aldana-Galván, Jose L. Alvarez-Rebollar, Juan Carlos Cataa-Salazar, Nestaly Marin-Nevárez, Erick Solís-Villareal, Jorge Urrutia, and Carlos Velarde. Beacon coverage in orthogonal polyhedra. In Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), pages 156-161, 2017. Google Scholar
  4. Israel Aldana-Galván, Jose L. Alvarez-Rebollar, Juan Carlos Cataa-Salazar, Nestaly Marin-Nevárez, Erick Solís-Villareal, Jorge Urrutia, and Carlos Velarde. Tight bounds for illuminating and covering of orthotrees with vertex lights and vertex beacons. Graphs and Combinatorics, 36:617-630, 2929. Google Scholar
  5. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geom. Appl., 5:75-91, 1995. URL: https://doi.org/10.1142/S0218195995000064.
  6. Sang Won Bae, Chan-Su Shin, and Antoine Vigneron. Tight bounds for beacon-based coverage in simple rectilinear polygons. Computational Geometry, 80:40-52, 2019. URL: https://doi.org/10.1016/j.comgeo.2019.02.002.
  7. Michael Biro. Beacon-based routing and guarding. PhD thesis, State University of New York at Stony Brook, 2013. Google Scholar
  8. Michael Biro, Jie Gao, Justin Iwerks, Irina Kostitsyna, and Joseph S. B. Mitchell. Beacon-based routing and coverage. In Proceedings of the 21st Fall Workshop on Computational Geometry, 2011. Google Scholar
  9. Michael Biro, Jie Gao, Justin Iwerks, Irina Kostitsyna, and Joseph S. B. Mitchell. Beacon based structures in polygonal domains. In Abstracts of the 1st Computa- tional Geometry: Young Researchers Forum, 2012. Google Scholar
  10. Michael Biro, Jie Gao, Justin Iwerks, Irina Kostitsyna, and Joseph S. B. Mitchell. Combinatorics of beacon routing and coverage. In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), 2013. Google Scholar
  11. Michael Biro, Justin Iwerks, Irina Kostitsyna, and Joseph S. B. Mitchell. Beacon-based algorithms for geometric routing. In 13th International Symposium on Algorithms and Data Structures (WADS 2013), pages 158-169, 2013. URL: https://doi.org/10.1007/978-3-642-40104-6_14.
  12. Prosenjit Bose and Thomas C. Shermer. Gathering by repulsion. Computational Geometry, 90:101627, 2020. URL: https://doi.org/10.1016/j.comgeo.2020.101627.
  13. Pierre Bouguer. Sur de nouvelles courbes ausquelle on peut donner le nom de linges de poursuite. Mémoires de mathématique et de physique tirés des registres de l’Académie royale des sciences, pages 1-14, 1732. URL: https://gallica.bnf.fr/ark:/12148/bpt6k35294.
  14. Johans Cleve and Wolfgang Mulzer. Combinatorics of beacon-based routing in three dimensions. Computational Geometry, 91:101667, 2020. URL: https://doi.org/10.1016/j.comgeo.2020.101667.
  15. Pierre de Maupertuis. Sure les courbes de poursuite. Mémoires de mathématique et de physique tirés des registres de l’Académie royale des sciences, pages 15-17, 1732. URL: https://gallica.bnf.fr/ark:/12148/bpt6k35294.
  16. John R. Gilbert, Joan P. Hutchinson, and Robert Endre Tarjan. A separator theorem for graphs of bounded genus. J. Algorithms, 5(3):391-407, 1984. URL: https://doi.org/10.1016/0196-6774(84)90019-1.
  17. Arthur S. Hathaway. Problems and solutions: Problem 2801. American Mathematical Monthly, 27(1):31, 1920. URL: https://doi.org/10.2307/2973244.
  18. Monika R. Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci., 55(1):3-23, 1997. URL: https://doi.org/10.1006/jcss.1997.1493.
  19. Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman, and David Rappaport. An Optimal Algorithm to Compute the Inverse Beacon Attraction Region. In 34th International Symposium on Computational Geometry (SoCG 2018), 2018. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.55.
  20. Bahram Kouhestani and David Rappaport. Edge patrolling beacon. In Abstracts from the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2017), pages 101-102, 2017. Google Scholar
  21. Bahram Kouhestani, David Rappaport, and Kai Salomaa. On the inverse beacon attraction region of a point. In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), 2015. Google Scholar
  22. Bahram Kouhestani, David Rappaport, and Kai Salomaa. The length of the beacon attraction trajectory. In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 69-74, 2016. Google Scholar
  23. Bahram Kouhestani, David Rappaport, and Kai Salomaa. Routing in a polygonal terrain with the shortest beacon watchtower. Computational Geometry, 68:34-47, 2018. URL: https://doi.org/10.1016/j.comgeo.2017.05.005.
  24. John E. Littlewood. Littlewood’s Miscallany: edited by Béla Bollobás. Cambridge University Press, 1986. Google Scholar
  25. Amirhossein Mozafari and Thomas C. Shermer. Transmitting particles in a polygonal domain by repulsion. In 12th International Conference on Combinatorial Optimization and Applications (COCOA 2018), pages 495-508, 2018. URL: https://doi.org/10.1007/978-3-030-04651-4_33.
  26. Paul J. Nahin. Chases and Escapes: The Mathematics of Pursuit and Evasion. Princeton University Press, 2007. Google Scholar
  27. Thomas C. Shermer. A combinatorial bound for beacon-based routing in orthogonal polygons. In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact