Speaker: Tran Tuan Viet
Time: 9h00, Wednesday, November 11, 2015 Location: Room 4, Building A14, Institute of Mathematics, 18 Hoang Quoc Viet, Cau Giay, Hanoi Abstract: We describe Pham Trong et al.'s algorithm for finding locally exact shortest paths between two points on a polyhedral surface (Pham Trong V., N. Szafran and L. Biard, Pseudo-geodesics on three-dimensional surfaces and pseudo-geodesic meshes, Numerical Algorithms, Vol. 26, 2001, pp. 305-315). Firstly, all the faces of the initial sequence of adjacent faces (constructed from polyhedral surface) are unfolded. Then, the shortest path between two points along the unfolded sequence is determined using beam propagation algorithm (proposed by Pham Trong et al.). It takes O(k^2) time complexity, where k is the number of the edges contained in the sequence of adjacent faces. Finally, we describe a updating technique for finding the sequence of adjacent faces which contains the (possibly local) shortest path between two points on polyhedral surfaces. |