WEEKLY ACTIVITIES

The funnel algorithm for finding the shortest paths between two specified points in an simple polygon
Speaker: Dang Ngoc Anh

Time: 14h, Wednesday, May 13, 2015

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

Abstract: 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.

Back

Highlights

23/04/24, Conference:
Some recent progress on selected problems in number theory
25/04/24, Conference:
Hội thảo Tối ưu và Tính toán khoa học lần thứ 22
28/05/24, Conference:
Hội nghị Đại số - Lý thuyết số - Hình hoc - Tô pô 2024
28/10/24, Conference:
School and Workshop “Selected topics in Arithmetic Algebraic Geometry”

New Scientiffic Publications