Event calendar file
School of Technology and Computer Science Seminars
A Near Optimal Algorithm for Finding Euclidean Shortest Path in Polygonal Domain
by Dr. R. Inkulu (Indian Institute of Technology, Guwahati)
Tuesday, July 13, 2010
from
to
(Asia/Kolkata)
at Colaba Campus ( A-212 )
at Colaba Campus ( A-212 )
| Description |
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.
|
| Organised by | John Barretto |
