On Chen and Han’s algorithm for finding the shortest paths on polyhedral surfaces
Speaker: Nguyen Thi My Hanh

Time: 14h00, Wednesday, December 2, 2015
Location:
Room 212, Building A5, Institute of Mathematics, 18 Hoang Quoc Viet, Cau Giay, Hanoi
Abstract:
In this report, we present Chen and Han's algorithm introduced in 1990 for determining the shortest path between two arbitrary points on the surface of a convex polyhedron or a non-convex polyhedron. The algorithm uses a "Continuous Dijkstra" technique based on the key observation “one angle one split” with O(n2) complexity. In addition, Kavena and O'Rourke's implementation in 2000 is presented.

Back