Document Open Access Logo

Shortest Paths in Portalgons

Authors Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, Frank Staals

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.48.pdf
  • Filesize: 4.77 MB
  • 16 pages

Document Identifiers

Author Details

Maarten Löffler
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
  • Department of Computer Science, Tulane University, New Orleans, LA, USA
Tim Ophelders
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
  • Department of Mathematics and Computer Science, TU Eindhoven, Tthe Netherlands
Rodrigo I. Silveira
  • Department de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain
Frank Staals
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands

Funding

  • Ophelders, Tim: Partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260.
  • Silveira, Rodrigo I.: Partially funded by MICINN through project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033.

Acknowledgements

We are grateful to the anonymous reviewers for the detailed and valuable feedback provided, which helped us to improve the paper considerably.

Cite As Get BibTex

Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals. Shortest Paths in Portalgons. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.48

Abstract

Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric.
We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons.
The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Polyhedral surfaces
  • shortest paths
  • geodesic distance
  • Delaunay triangulation

Metrics

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

Related Versions

References

  1. Pankaj K. Agarwal, Boris Aronov, Joseph O'Rourke, and Catherine A. Schevon. Star unfolding of a polytope with applications. SIAM Journal on Computing, 26(6):1689-1713, 1997. URL: https://doi.org/10.1137/S0097539793253371.
  2. Boris Aronov and Joseph O'Rourke. Nonoverlap of the star unfolding. Discrete & Computational Geometry, 8(3):219-250, 1992. Google Scholar
  3. Alexander I Bobenko and Boris A Springborn. A discrete Laplace-Beltrami operator for simplicial surfaces. Discrete & Computational Geometry, 38(4):740-756, 2007. Google Scholar
  4. Vincent Borrelli, Saïd Jabrane, Francis Lazarus, and Boris Thibert. Flat tori in three-dimensional space and convex integration. Proceedings of the National Academy of Sciences, 109(19):7218-7223, 2012. URL: https://doi.org/10.1073/pnas.1118478109.
  5. Jindong Chen and Yijie Han. Shortest paths on a polyhedron. Int. J. Comput. Geom. Appl., 6(2):127-144, 1996. URL: https://doi.org/10.1142/S0218195996000095.
  6. Valve Corporation. Portal, 2007. Video game. Google Scholar
  7. Yu. D. Burago V. A. Zalgaller (Eds.). Geometry III: Theory of Surfaces. Springer Verlag, 1993. Google Scholar
  8. H Ellison. The city on the edge of forever, 1967. Star Trek, season 1, episode 28. Google Scholar
  9. Jeff Erickson. Ernie’s 3d pancakes: Shortest paths on pl surfaces, 2006. March 14, 2023. URL: https://3dpancakes.typepad.com/ernie/2006/03/shortest_paths_.html.
  10. Jeff Erickson and Amir Nayyeri. Tracing compressed curves in triangulated surfaces. Discret. Comput. Geom., 49(4):823-863, 2013. URL: https://doi.org/10.1007/s00454-013-9515-z.
  11. Leonidas Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences, 39(2):126-152, 1989. URL: https://doi.org/10.1016/0022-0000(89)90041-X.
  12. Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1):209-233, 1987. URL: https://doi.org/10.1007/BF01840360.
  13. John Hershberger and Subhash Suri. An Optimal Algorithm for Euclidean Shortest Paths in the Plane. SIAM Journal on Computing, 28(6):2215-2256, 1999. Google Scholar
  14. Biliana Kaneva and Joseph O'Rourke. An implementation of Chen & Han’s shortest paths algorithm. URL: http://cs.smith.edu/~jorourke/Papers/shortest.ps.gz.
  15. Stephen Kiazyk, Sébastien Loriot, and Éric Colin de Verdière. Triangulated surface mesh shortest paths. URL: https://doc.cgal.org/latest/Surface_mesh_shortest_path/index.html.
  16. Francis Lazarus and Florent Tallerie. A Universal Triangulation for Flat Tori. CoRR, March 2022. URL: https://arxiv.org/abs/2203.05496.
  17. Yong-Jin Liu, Chun-Xu Xu, Dian Fan, and Ying He. Efficient Construction and Simplification of Delaunay Meshes. ACM Transactions on Graphics, 34(6):1-13, 2015. URL: https://doi.org/10.1145/2816795.2818076.
  18. Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals. Shortest paths in portalgons. CoRR, 2023. URL: https://arxiv.org/abs/2303.08937.
  19. A.D. Milka. Multidimensional spaces with polyhedral metric of nonnegative curvature I. Ukrain. Geom. Sb., 5(6):103-114, 1968. In Russian. Google Scholar
  20. Joseph S. B. Mitchell. A new algorithm for shortest paths among obstacles in the plane. Annals of Mathematics and Artificial Intelligence, 3(1):83-105, March 1991. URL: https://doi.org/10.1007/BF01530888.
  21. Joseph S. B. Mitchell. Shortest paths and networks. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Toth, editors, Handbook of Discrete and Computational Geometry, Third Edition, pages 811-848. Chapman and Hall/CRC, 2017. Google Scholar
  22. Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. The discrete geodesic problem. SIAM J. Comput., 16(4):647-668, 1987. URL: https://doi.org/10.1137/0216045.
  23. Joseph S. B. Mitchell and Christos H. Papadimitriou. The weighted region problem: Finding shortest paths through a weighted planar subdivision. J. ACM, 38(1):18-73, 1991. URL: https://doi.org/10.1145/102782.102784.
  24. Yevgeny Schreiber. An optimal-time algorithm for shortest paths on realistic polyhedra. Discret. Comput. Geom., 43(1):21-53, 2010. URL: https://doi.org/10.1007/s00454-009-9136-8.
  25. A. Wachowski and L. Wachowski. Matrix revolutions, 2003. Warner Bros. Motion picture. Google Scholar
  26. Haitao Wang. A new algorithm for Euclidean shortest paths in the plane. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 975-988, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451037.
  27. Haitao Wang. Shortest paths among obstacles in the plane revisited. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 810-821. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.51.
  28. Shi-Qing Xin and Guo-Jin Wang. Improving Chen and Han’s algorithm on the discrete geodesic problem. ACM Trans. Graph., 28(4), September 2009. URL: https://doi.org/10.1145/1559755.1559761.
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 About DROPS Imprint Privacy Contact