Tata Institute of Fundamental Research
A Near Optimal Algorithm for Finding Euclidean Shortest Path in Polygonal Domain
Seminar
Speaker:
R. Inkulu
Indian Institute of Technology
Department of Computer Science
and Engineering
Guwahati
http://
Date:
Tuesday, 13 Jul 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | R. Inkulu Indian Institute of Technology Department of Computer Science and Engineering Guwahati http:// |
| Date: | Tuesday, 13 Jul 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.