Date: Wed 15 Jul
Time: 15.00
Place: room 322

Speaker: Prof. J.R. Sack (Carleton Univ., Ottawa, Canada)
Title: Approximating Weighted Shortest Paths on Polyhedral Surfaces
Reference: Leila de Floriani, Paola Magillo

Abstract. 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.