Người báo cáo: Đặng Thị Ngọc Ánh
Thời gian: 9h, Thứ 4, ngày 4/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: Finding the shortest path between two points (source, destination) has been solved by many O(n^2) time algorithms. In this report, we will present Lee & Preparata's paper in Networks journal published in 1984. An O(n) time algorithm is developed by constructing the shortest-path tree with the edges belonging the inward-convex chains of the boundary of the funnels. The inward-convex chains are the shortest paths from the source to the vertices of the diagonals and to the destination, the funnel is the region delimited by these chains and diagonals respectively, the diagonal is a line segment which connects two nonadjacent vertexs of the polygon. |
