## Speaker:

Jorg-Rudiger Sack, Carleton University, Ottawa, Canada

## Title:

Approximating Weighted Shortest Paths on Polyhedral Surfaces*

## Location:

Archway 2

## Abstract:

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.