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

## Speaker:

R. Inkulu Indian Institute of Technology Department of Computer Science and Engineering Guwahati http://

## Time:

Tuesday, 13 July 2010 (All day)

## Venue:

• 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.