Thanh An Phan: Funnel Technique for Finding Shortest Paths from Source Point to all Destination Points on a Convex Polyhedral Surface
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