Funnels for finding shortest paths between two points along a sequence of triangles in 3D
Speaker: Dinh Thanh Giang

Time: 14h, Friday, September 18, 2015

Location: Room 4, Building A14, Institute of Mathematics, 18 Hoang Quoc Viet, Cau Giay, Hanoi

Abstract: In this report, we present a linear algorithm for finding the shortest path between two points along a sequence of triangles in three-dimensional space. The concept of ``funnels" along a sequence of triangles is introduced, that is similar to Lee and Preparata's one in a simple polygon. We prove that unfolding a funnel on its adjacent triangle gives a simple polygon and hence can be used for constructing next funnel. The sequence of funnels is constructed iteratively and then the shortest path between two points along the sequence of triangles is determined by cusps of these funnels.

This is a joint work with P. T. An, H. X. Phu and K. Polthier.

Back