Thanh An Phan, Institute of Mathematics, Hanoi

In this paper, we present an O(n^{2}) algorithm for finding the exact shortest paths from a fixed source point to all other points on a triangulated polyhedral surface of a convex polytope in three-dimensional space using the concept of funnels on the surface. Our algorithm builds the sequence tree by recursively splitting funnels. Because of special shape of these funnels (their left boundaries are straightest geodesics), funnels are determined explicitly and do not rely on unfolding technique. Number of operations in our algorithm is relatively small comparing with the number of operations in Chen and Han's algorithm, 1990.

Nov 24, 2016 | 03:00 PM

FU Berlin | Arnimallee 6 | Raum 108/109