Wed 15 Jul
Prof. J.R. Sack (Carleton Univ., Ottawa, Canada)
Approximating Weighted Shortest Paths on Polyhedral Surfaces
Leila de Floriani, Paola Magillo
Shortest path problems are among the fundamental problems
studied in computational geometry. In this talk accompanied
by a video, we consider the problem of computing a shortest
cost path between two points on a (possibly non-convex)
polyhedral surface. The surface is composed of triangular
regions (faces) in which each region has an associated
positive weight indicating the cost of travel in that region.
Most shortest path applications demand simple and efficient
algorithms to compute approximate shortest paths as opposed
to a complex algorithm that computes an exact path. Polyhedra
arising in these applications approximate real surfaces and thus
an approximate path will typically suffice. Our interest is also
motivated by our research and development on a parallel system
for GIS and spatial modeling.
The talk describes several schemes that allow the computation of
approximate shortest paths on polyhedral surfaces in both the
weighted and unweighted scenarios. The schemes are based on
adding Steiner points along the polyhedral edges and interconnecting
them across each face.
The schemes vary in the way in which the Steiner points and edges are
added. We represent the Steiner points and edges as a graph in which
we compute an approximate path using Dijkstra's graph shortest path
algorithm. We show that as more and more Steiner points are added,
we obtain increasing path accuracy and with only a few (constant
number of) Steiner points per polyhedral edge, the path cost
converges to a near-optimal value.
We have implemented these schemes as well as Chen and Han's shortest
path algorithm. Each of the schemes is described in the video shown
and we also give experimental results that show how well they
performed on the test suite of terrain data that we used.
We will also present some new theoretical results on
epsilon-approximation algorithms for shortest paths on
weighted/unweighted polyhedral terrains.