Thanh An Phan: Funnel Technique for Finding Shortest Paths from Source Point to all Destination Points on a Convex Polyhedral Surface

Nov 24, 2016 | 03:00 PM

Location

Thanh An Phan, Institute of Mathematics, Hanoi

In this paper, we present an O(n2) 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.

Time & Location

Nov 24, 2016 | 03:00 PM

FU Berlin | Arnimallee 6 | Raum 108/109