Người báo cáo: Nguyễn Thị Mỹ Hạnh
Thời gian: 14h, Thứ 4, ngày 6/1/2016
Địa điểm: Phòng 4, Nhà A14, Viện Toán học, 18 Hoàng Quốc Việt, Cầu Giấy, Hà Nội
Tóm tắt: 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. |
