Người báo cáo: Trần Tuấn Việt
Thời gian: 9h, Thứ 4, ngày 11/11/2015 Địa điểm: Phòng số 4, nhà A14, Viện Toán học, 18 Hoàng Quốc Việt, Hà Nội Tóm tắt: 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. |