Shortest path problems are among the fundamental problems studied in graph theory and computational geometry. Practical problems arise in applications areas such as robotics, traffic control, search and rescue, water flow analysis, road design, navigation, routing, geographical information systems. Most of these applications demand simple and efficient algorithms to compute approximate shortest paths as opposed to a complex algorithm that computes an exact path.
Motivated by the practical importance of these problems and very high complexities for computing exact shortest paths (in particular in weighted scenarios or in 3D) we investigate algorithms for computing approximated shortest paths. In this talk we describe several simple and practical algorithms (schemes) to compute an approximated weighted (and unweighted) shortest path between two points on the surface of a (possibly, non-convex) polyhedron (or a TIN).
We also describe ‘µ-approximation algorithms for such problems. While these algorihtms have a more complex analysis their implementation remains simple. Furthermore, we sketch our work on shortest anisotropic paths on terrains. Anisotropic path costs take into account the length of the path traveled, possibly weighted, and the direction of travel along the faces of the terrain. Considering faces to be weighted has added realism to the study of (pure) Euclidean shortest paths. Parameters such as the varied nature of the terrain, friction, or slope of each face, can be captured via face weights. Anisotropic paths add further realism by taking into consideration the direction of travel on each face thereby e.g., eliminating paths that are too steep for vehicles to travel and preventing the vehicles from turning over.
Finally, we discuss some very recent developments in computing shortest paths in 2-D and 3-D.
Research is supported in part by NSERC and SUN Microsystems.
Last modified: Monday, 14-Mar-2005 10:07:54 NZDT
This page is maintained by Caroline Wills.