A Near Optimal Algorithm for Finding Euclidean Shortest Path in Polygonal Domain

R. Inkulu Indian Institute of Technology Department of Computer Science and Engineering Guwahati http://
Tuesday, 13 Jul 2010 (all day)
A-212 (STCS Seminar Room)
The Euclidean shortest path problem in a polygonal region is one of the oldest and best-known in Computational Geometry due to its various applications. Given a polygon with holes $P$ and two points $s$ and $t$ interior to it, our algorithm finds an Euclidean shortest path from $s$ to $t$ in $O(n+m(\\lg{m})(\\lg{n}))$ time using $O(n)$ space. Here, $n$ is the number of vertices in the given polygonal domain, and $m$ is the number of holes. This problem is listed as part of The Open Problems Project, which intends for a solutions with $O(n+m(\\lg{m}))$ time using $O(n)$ space. After identifying hourglasses in $P$, the regions of interest in $P$ are traversed with the shortest path wavefront.