22/06/2011, 15:00 — 16:00 — Sala P3.10, Pavilhão de Matemática
Phan Than An, CEMAT/IST
Convexity helps solve some shortest path problems
To date, solving shortest path problems inside simple polygons has usually relied on triangulation of the polygons and graph theory. The question: "Can one devise a simple $O(n)$ time algorithm for computing the shortest path between two points in a simple polygon (with $n$ vertices), without resorting to a (complicated) linear-time triangulation algorithm?" raised by J. S.B. Mitchell in Handbook of Computational Geometry (J. Sack and J. Urrutia, eds., Elsevier Science B.V., 2000), is still open. The aim of this talk is to show that convexity contributes to the design of efficient algorithms for solving some versions of shortest path problems (namely, computing the convex hull of a finite set of points in 2D and 3D, computing the convex rope/shortest path between two points outside/inside a simple polygon) without triangulation of polygons or graph theory. Numerical examples are presented.
