The role of graph for solving some geometric shortest path problems in 2D and 3D

Lecture Notes in Electrical Engineering, 279 (2014), 179-184
http://dx.doi.org/10.1007/978-3-642-41674-3_27

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.