Abstract
Determining Euclidean shortest paths between two points in a domain is a fundamental problem in computing geometry and has many applications in GIS, robotics, computer graphics, CAD, etc. To date, solving Euclidean shortest path problems inside simple polygons has usually relied on triangulation of the entire polygons and graph theory. The question: "Can one devise a simple O(n) time algorithm for computing the shortest path between two points in a simple polygon (with n vertices), without resorting to a (complicated) linear-time triangulation algorithm?" raised by J. S.B. Mitchell in Handbook of Computational Geometry (J. Sack and J. Urrutia, eds., Elsevier Science B.V., 2000), is still open. The aim of this paper is to show that in 2D, convexity contributes to the design of an efficient algorithm for finding the approximate shortest path between two points inside a simple polygon without triangulation of the entire polygons or graph theory. Conversely, in 3D, we show that graph tools (e.g., Dijkstra’s algorithm for solving shortest path problems on graphs) are crucial to find an Euclidean shortest path between two points on the surface of a convex polytope.
This work received financial support from Portuguese National Funds through FCT (Fundação para a Ciência e a Tecnologia) under the scope of project Pest-OE/MAT/UI0822/2011 and the National Foundation for Science and Technology Development, Vietnam (NAFOSTED) under grant number 101.02-2011.45.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
An, P.T., Hai, N.N., Hoai, T.V.: The role of convexity for solving some shortest path problems in plane without triangulation. In: International Conference on Mathematical Sciences and Statistics, Kuala Lump, Malaysia, February 5-7. AIP Conference Proceedings, American Institute of Physics, NY (2013)
An, P.T., Hai, N.N., Hoai, T.V.: Direct multiple shooting method for solving approximate shortest path problems. Journal of Computational and Applied Mathematics 244, 67–76 (2013)
An, P.T., Hai, N.N., Hoai, T.V., Trang, L.H.: On the performance of trangulation-based multiple shooting method for 2D shortest path problems. In: International Conference on Advanced Computing and Applications (ACOMP 2013), Ho Chi Minh City, Vietnam, October 23-25 (2013)
An, P.T.: Reachable grasps on a polygon of a robot arm: finding convex ropes without triangulation. Journal of Robotics and Automation 25(4), 304–310 (2010)
An, P.T.: Method of orienting curves for determining the convex hull of a finite set of points in the plane. Optimization 59(2), 175–179 (2010)
An, P.T., Hoai, T.V.: Incremental convex hull as an orientation to solving the shortest path problem. In: IEEE Proc. 3rd Int. Conf. Comp. & Auto. Eng., Chongqing, China, January 21-23 (2011)
Bock, H.G., Plitt, K.J.: A multiple shooting algorithm for direct solution optimal control problems. In: Proceedings of the 9th IFAC World Congress, Budapest, pp. 243–247. Pergamon Press (1984)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)
Lee, D.T., Preparata, F.P.: Euclidean shortest paths in the presence of rectilinear barriers. Networks 14, 393–410 (1984)
Li, F., Klette, R.: Euclidean Shortest Paths: Exact or Approximate Algorithms. Springer (2011)
Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633–701. Elsevier Science B. V. (2000)
Peshkin, M.A., Sanderson, A.C.: Reachable grasps on a polygon: the convex rope algorithm. IEEE Journal on Robotics and Automation 2(1), 53–58 (1986)
Phu, H.X.: Ein konstruktives Loesungsverfahren fuer das Problem des Inpolygons kleinsten Umfangs von J. Steiner. Optimization 18, 349–359 (1987)
O’Rourke, J.: Computational Geometry in C, 2nd edn. Cambridge University Press (1998)
Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362–394 (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
An, P.T., Hai, N.N., Van Hoai, T. (2014). The Role of Graph Theory in Solving Euclidean Shortest Path Problems in 2D and 3D. In: Jeong, H., S. Obaidat, M., Yen, N., Park, J. (eds) Advances in Computer Science and its Applications. Lecture Notes in Electrical Engineering, vol 279. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41674-3_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-41674-3_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41673-6
Online ISBN: 978-3-642-41674-3
eBook Packages: EngineeringEngineering (R0)