Shortest paths in 2-d and 3-d

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. In this talk, we
survey algorithms to compute weighted and unweighted shortest paths.
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 have investigated algorithms for computing
approximated shortest paths. While the analysis of some of these
algorithms is somewhat challenging, their implementation often remains
simple. The algorithms are thus of interest to theoreticians and
practitioners.

For more info on Fejes Tóth Lectures see

http://ccdg.math.ucalgary.ca/news-events/events/talks