HOẠT ĐỘNG TRONG TUẦN

Thuật toán hình phễu tìm đường đi ngắn nhất giữa hai điểm trong một đa giác đơn
Người báo cáo: Đặng Ngọc Ánh

Thời gian: 14h, Thứ 4, ngày 13/5/2015

Địa điểm: Phòng 6, 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: The problem of finding the shortest paths between two specified points (source, destination) in the plane has been solved by many O(n^2) time algorithms. In this report, we will present Lee & Preparata's paper, an O(nlogn) time algorithm can be developed which solves the problem by constructing the shortest-path tree with the edges belonging the inward-convex chains of the boundary of the funnels. The inward-convex chains were the shortest paths from the source to all the vertices of the obstacles and to the destination. The funnel is the region delimited by these chains and obstacles respectively.

Trở lại

Công bố khoa học mới