Document Open Access Logo

On Flipping the Fréchet Distance

Authors Omrit Filtser , Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.51.pdf
  • Filesize: 1.1 MB
  • 22 pages

Document Identifiers

Author Details

Omrit Filtser
  • The Open University of Israel, Ra'anana, Israel
Mayank Goswami
  • Queens College CUNY, Flushing, NY, USA
Joseph S. B. Mitchell
  • Stony Brook University, NY, USA
Valentin Polishchuk
  • Linköping University, Sweden

Funding

  • Filtser, Omrit: This work is supported by the Eric and Wendy Schmidt Fund for Strategic Innovation, by the Council for Higher Education of Israel, and by Ben-Gurion University of the Negev.
  • Goswami, Mayank: This work is supported by US National Science Foundation (NSF) awards CRII-1755791 and CCF-1910873.
  • Mitchell, Joseph S. B.: This work is partially supported by the National Science Foundation (CCF-2007275), the US-Israel Binational Science Foundation (BSF project 2016116), Sandia National Labs, and DARPA (Lagrange).
  • Polishchuk, Valentin: This work is supported by grants from the Swedish Research Council and the Swedish Transport Administration

Acknowledgements

We thank the anonymous reviewers for their many helpful comments. We thank the many participants of the Stony Brook CG Group, where discussions about geometric social distancing problems originated in Spring 2020, as the COVID-19 crisis expanded worldwide. We would also like to thank Gaurish Telang for helping to solve a system of non-linear equations.

Cite AsGet BibTex

Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk. On Flipping the Fréchet Distance. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.51

Abstract

The classical and extensively-studied Fréchet distance between two curves is defined as an inf max, where the infimum is over all traversals of the curves, and the maximum is over all concurrent positions of the two agents. In this article we investigate a "flipped" Fréchet measure defined by a sup min - the supremum is over all traversals of the curves, and the minimum is over all concurrent positions of the two agents. This measure produces a notion of "social distance" between two curves (or general domains), where agents traverse curves while trying to stay as far apart as possible. We first study the flipped Fréchet measure between two polygonal curves in one and two dimensions, providing conditional lower bounds and matching algorithms. We then consider this measure on polygons, where it denotes the minimum distance that two agents can maintain while restricted to travel in or on the boundary of the same polygon. We investigate several variants of the problem in this setting, for some of which we provide linear time algorithms. Finally, we consider this measure on graphs. We draw connections between our proposed flipped Fréchet measure and existing related work in computational geometry, hoping that our new measure may spawn investigations akin to those performed for the Fréchet distance, and into further interesting problems that arise.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
Keywords
  • curves
  • polygons
  • distancing measure

Metrics

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

Related Versions

References

  1. Helmut Alt, Alon Efrat, Günter Rote, and Carola Wenk. Matching planar maps. Journal of algorithms, 49(2):262-283, 2003. Google Scholar
  2. 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.
  3. Esther M. Arkin, Joseph S. B. Mitchell, and Valentin Polishchuk. Maximum thick paths in static and dynamic environments. Comput. Geom., 43(3):279-294, 2010. URL: https://doi.org/10.1016/j.comgeo.2009.02.007.
  4. Christoph Baur and Sándor P. Fekete. Approximation of geometric dispersion problems. Algorithmica, 30(3):451-470, 2001. URL: https://doi.org/10.1007/s00453-001-0022-x.
  5. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. of the 55th IEEE Annual Symposium on Foundations of Computer Science FOCS, pages 661-670, 2014. URL: https://doi.org/10.1109/FOCS.2014.76.
  6. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. JoCG, 7(2):46-76, 2016. URL: https://doi.org/10.20382/jocg.v7i2a4.
  7. Kevin Buchin, Tim Ophelders, and Bettina Speckmann. SETH says: Weak Fréchet distance is faster, but only if it is continuous and in one dimension. In Proc. of the 30th Annual Symposium on Discrete Algorithms SODA, pages 2887-2901. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.179.
  8. Timothy H. Chung, Geoffrey A. Hollinger, and Volkan Isler. Search and pursuit-evasion in mobile robotics - A survey. Auton. Robots, 31(4):299-316, 2011. URL: https://doi.org/10.1007/s10514-011-9241-4.
  9. Atlas Cook and Carola Wenk. Geodesic Fréchet distance inside a simple polygon. ACM Transactions on Algorithms (TALG), 7(1):1-19, 2010. Google Scholar
  10. Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Henk Meijer, and Christian Scheffer. Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch. SIAM J. Comput., 48(6):1727-1762, 2019. URL: https://doi.org/10.1137/18M1194341.
  11. Adrian Dumitrescu and Günter Rote. On the fréchet distance of a set of curves. In Proceedings of the 16th Canadian Conference on Computational Geometry, CCCG'04, Concordia University, Montréal, Québec, Canada, August 9-11, 2004, pages 162-165, 2004. URL: http://www.cccg.ca/proceedings/2004/39.pdf.
  12. Thomas Eiter and Heikki Mannila. Computing discrete Fréchet distance. Technical report, Citeseer, 1994. Google Scholar
  13. Sándor P. Fekete and Henk Meijer. Maximum dispersion and geometric maximum weight cliques. Algorithmica, 38(3):501-511, 2004. URL: https://doi.org/10.1007/s00453-003-1074-x.
  14. Greg N. Frederickson and Donald B. Johnson. Generalized selection and ranking: Sorted matrices. SIAM J. Comput., 13(1):14-30, 1984. URL: https://doi.org/10.1137/0213002.
  15. Leonidas J Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences, 39(2):126-152, 1989. Google Scholar
  16. Shai Hirsch and Dan Halperin. Hybrid motion planning: Coordinating two discs moving among polygonal obstacles in the plane. In Jean-Daniel Boissonnat, Joel W. Burdick, Ken Goldberg, and Seth Hutchinson, editors, Algorithmic Foundations of Robotics V, Selected Contributions of the Fifth International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002, Nice, France, December 15-17, 2002, volume 7 of Springer Tracts in Advanced Robotics, pages 239-256. Springer, 2002. URL: https://doi.org/10.1007/978-3-540-45058-0_15.
  17. Tien-Ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, and Joseph S. B. Mitchell. Algorithms for rapidly dispersing robot swarms in unknown environments. In Jean-Daniel Boissonnat, Joel W. Burdick, Ken Goldberg, and Seth Hutchinson, editors, Algorithmic Foundations of Robotics V, Selected Contributions of the Fifth International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002, Nice, France, December 15-17, 2002, volume 7 of Springer Tracts in Advanced Robotics, pages 77-94. Springer, 2002. URL: https://doi.org/10.1007/978-3-540-45058-0_6.
  18. Patrick A. O'Donnell and Tomás Lozano-Pérez. Deadlock-free and collision-free coordination of two robot manipulators. In Proceedings of the 1989 IEEE International Conference on Robotics and Automation, Scottsdale, Arizona, USA, May 14-19, 1989, pages 484-489. IEEE Computer Society, 1989. URL: https://doi.org/10.1109/ROBOT.1989.100033.
  19. Richard Pollack, Micha Sharir, and Günter Rote. Computing the geodesic center of a simple polygon. Discrete & Computational Geometry, 4(6):611-626, 1989. Google Scholar
  20. Christian Scheffer. Train scheduling: Hardness and algorithms. In M. Sohel Rahman, Kunihiko Sadakane, and Wing-Kin Sung, editors, WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Singapore, March 31 - April 2, 2020, Proceedings, volume 12049 of Lecture Notes in Computer Science, pages 342-347. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-39881-1_30.
  21. Christian Scheffer. Scheduling three trains is np-complete. In J. Mark Keil and Debajyoti Mondal, editors, Proceedings of the 32nd Canadian Conference on Computational Geometry, CCCG 2020, August 5-7, 2020, University of Saskatchewan, Saskatoon, Saskatchewan, Canada, pages 87-93, 2020. Google Scholar
  22. Michail I Schlesinger, EV Vodolazskiy, and VM Yakovenko. Similarity of closed polygonal curves in Fréchet metric. arXiv preprint, 2014. URL: http://arxiv.org/abs/1409.4613.
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