Abstract

We present some analytical and geometric properties of shortest ordered paths joining two given points with respect to a sequence of line segments in a Euclidean space, especially their existence, uniqueness, characteristics, and conditions for concatenation of two shortest ordered paths to be a shortest ordered path. We then focus on straightest paths lying on a sequence of adjacent convex polygons in 2 or 3 dimensional spaces.

Author information

Contact details are reproduced from the original publication and may be historical.

Nguyen Ngoc Hai

Department of Mathematics, International University, Vietnam National University, Ho Chi Minh City, Vietnam

nnhai@hcmiu.edu.vn

Phan Thanh An

Institute of Mathematics and Computer Science, University of São Paulo, São Carlos – SP, Brasil and: Institute of Mathematics, Vietnam Academy of Science and Technology, Cau Giay, Hanoi, Vietnam

thanhan@math.ac.vn

Phong Thi Thu Huyen

Institute of Mathematics, Vietnam Academy of Science and Technology, Cau Giay, Hanoi, Vietnam

ptthuyen@math.ac.vn

Keywords

  • Shortest paths
  • ordered paths
  • shortest ordered paths
  • straightest paths
  • concatenation of paths

Mathematics Subject Classification

65K10, 52B05, 52B55, 51M20

References

  1. P. K. Agarwal, S. Har-Peled, M. Karia: Computing approximate shortest paths on convex polytopes, Algorithmica 33(2) (2002) 227–242.https://doi.org/10.1007/s00453-001-0111-xGoogle Scholar
  2. A. Ahadi, A. Mozafari, A. Zarei: Touring a sequence of disjoint polygons: Complexity and extension, Theoretical Computer Science 556 (2014) 45–54.https://doi.org/10.1016/j.tcs.2014.06.019Google Scholar
  3. M. Ahmed, S. Das, S. Lodha, A. Lubiw, A. Maheshwari, S. Roy: Approximation algorithms for shortest descending paths in terrains, J. Discrete Alg. 8 (2010) 214–230.https://doi.org/10.1016/j.jda.2009.05.001Google Scholar
  4. M. Ahmed, A. Lubiw: Shortest descending paths: towards an exact algorithm, Internat. J. Comput. Geom. Appl. 21 (2011) 431–466.https://doi.org/10.1142/S0218195911003755Google Scholar
  5. M. Ahmed, A. Lubiw, A. Maheshwari: Shortest gently descending paths, WALCOM (2009) 59–70.https://doi.org/10.1007/978-3-642-00202-1_6Google Scholar
  6. L. Aleksandrov, A. Maheshwari, J.-R. Sack: Determining approximate shortest paths on weighted polyhedral surfaces, J. ACM 52 (2005) 25–53.https://doi.org/10.1145/1044731.1044733Google Scholar
  7. P. T. An: Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves, Optimization 67 (2018) 159–177.https://doi.org/10.1080/02331934.2017.1387260Google Scholar
  8. P. T. An, N. N. Hai, T. V. Hoai: Direct multiple shooting method for solving approximate shortest path problems, J. Comput. Appl. Math. 244 (2013) 67–76.https://doi.org/10.1016/j.cam.2012.11.001Google Scholar
  9. C. Bajaj: The algebraic complexity of shortest paths in polyhedral spaces, in: Proceedings 23rd Annual Allerton Conference on Communication, Control and Computing, University of Illinois, Monticello (1985) 510-517.Google Scholar
  10. M. Balasubramanian, J. R. Polimeni, E. L. Schwartz: Exact geodesics and shortest paths on polyhedral surfaces, IEEE Trans. Pattern Analysis Machine Intelligence 31(6) (2009)1006–1016.https://doi.org/10.1109/TPAMI.2008.213Google Scholar
  11. P. Bose, A. Maheshwari, C. Shu, S. Wuhrer: A survey of geodesic paths on 3d surfaces, Comput. Geom. 44 (2011) 486–4980.https://doi.org/10.1016/j.comgeo.2011.05.006Google Scholar
  12. J. Canny, J. Reif: Lower bounds for shortest path and related problems, in: Proceedings 28th Annual Symposium on Foundations of Computer Science, FOCS (1987) 49–60.https://doi.org/10.1109/SFCS.1987.42Google Scholar
  13. J. Chen, Y. Han: Shortest paths on a polyhedron. I: Computing shortest paths, Internat. J. Comput. Geom. Appl. 6(2) (1996) 127–144.https://doi.org/10.1142/S0218195996000095Google Scholar
  14. S.-W. Cheng, J. Jin: Approximate shortest descending paths, in: Proceedings 24th Annual ACM-SIAM Symposium Discrete Algebra (2013) 144–155.https://doi.org/10.1137/1.9781611973105.11Google Scholar
  15. S.-W. Cheng, J. Jin: Shortest paths on polyhedral surfaces and terrains, in: STOC ’14, Proceedings 46th Annual ACM Symposium on Theory of Computing (2014) 373–382.https://doi.org/10.1145/2591796.2591821Google Scholar
  16. A. F. Cook IV, C. Wenk: Shortest path problems on a polyhedral surface, Algorithmica 69 (2014) 58–77.https://doi.org/10.1007/s00453-012-9723-6Google Scholar
  17. M. Dror, A. Efrat, A. Lubiw: Touring a sequence of polygons, in: STOC ’03, Proceedings 35th Annual ACM Symposium on Theory of Computing (2003) 473–482.https://doi.org/10.1145/780542.780612Google Scholar
  18. N. N. Hai, P. T. An: A generalization of Blaschke’s convergence theorem in metric spaces, J. Convex Analysis 20(4) (2013) 1013–1024.https://doi.org/10.68381/jca20055Google Scholar
  19. T. V. Hoai, P. T. An, N. N. Hai: Multiple shooting approach for computing approximately shortest paths on convex polytopes, J. Comput. Appl. Math. 317 (2017) 235–246.https://doi.org/10.1016/j.cam.2016.10.026Google Scholar
  20. J. S. B. Mitchell: Geometric shortest paths and network optimizations, in: The Handbook of Computational Geometry, Chapter 15, Elsevier Science (2000) 633–701.https://doi.org/10.1016/B978-044482537-7/50016-4Google Scholar
  21. J. S. B. Mitchell: Approximation schemes for geometric network optimization problems, in: Encyclopedia of Algorithms, M.-Y. Kao (ed.), Springer, Berlin (2015).https://doi.org/10.1007/978-3-642-27848-8_505-1Google Scholar
  22. J. S. B. Mitchell, D. M. Mount, C. H. Papadimitriou: The discrete geodesic problem, SIAM J. Computing 16(4) (1987) 633–701.https://doi.org/10.1137/0216045Google Scholar
  23. J. S. B. Mitchell, C. H. Papadimitriou: The weighted region problem: finding shortest paths through a weighted planar subdivision, J. ACM 38 (1991) 18–73.https://doi.org/10.1145/102782.102784Google Scholar
  24. J. O’Rourke, S. Suri, H. Booth: Shortest paths on polyhedral surfaces, in: Theoretical Aspects of Computer Science, Lect. Notes Comput. Sci. 182 (1985) 243–254.https://doi.org/10.1007/BFb0024013Google Scholar
  25. A. Papadopoulos: Metric Spaces, Convexity and Nonpositive Curvature, 2nd edition, European Mathematical Society, Zurich (2014).https://doi.org/10.4171/132Google Scholar
  26. V. Pham-Trong, N. Szafran, L. Biard: Pseudo-geodesics on three-dimensional surfaces and pseudo-geodesic meshes, Numerical Algorithms 26(4) (2001) 305–315.https://doi.org/10.1023/A:1016617010088Google Scholar
  27. K. Polthier, M. Schmies: Straightest geodesics on polyhedral surfaces, in: Mathematical Visualization, H.-C. Hege et al. (eds.), International Workshop Visualization and Mathematics, Springer, Berlin (1998) 135–150.https://doi.org/10.1007/978-3-662-03567-2_11Google Scholar
  28. J. A. Sethian: Fast marching methods, SIAM Rev. 41(2) (1999) 199–235.https://doi.org/10.1137/S0036144598347059Google Scholar
  29. M. Sharir, A. Schorr: On shortest paths in polyhedral spaces, SIAM J. Comput. 15(1) (1986) 193–215.https://doi.org/10.1137/0215014Google Scholar
  30. J. Steiner: Gesammelte Werke, Band 2, Reimer, Berlin (1882).https://doi.org/10.1515/9783111611716Google Scholar
  31. K. R. Varadarajan, P. K. Agarwal: Approximating shortest paths on a nonconvex polyhedron, SIAM J. Computing 30(4) (2000) 1321–1340.https://doi.org/10.1137/S0097539799352759Google Scholar
  32. S.-Q. Xin, G.-J. Wang: Efficiently determining a locally shortest path on polyhedral surfaces, Computer-Aided Design 39(12) (2007) 1081–1090.https://doi.org/10.1016/j.cad.2007.08.001Google Scholar

Suggested citation

N. N. Hai, P. T. An, P. T. T. Huyen. “Shortest Paths along a Sequence of Line Segments in Euclidean Spaces.” Journal of Convex Analysis 26 (2019), No. 4, 1089–1112. https://doi.org/10.68381/jca26060

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2019. Rights now held by Banach Press LLC.