A near optimal algorithm for finding Euclidean shortest path in polygonal domain
A near optimal algorithm for finding Euclidean shortest path in polygonal domain
复制标题
多边形域欧氏最短路径的近最优算法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Maheshwari
中科院分区：
文献类型：
--
作者：
R. Inkulu;S. Kapoor;S. Maheshwari
We present an algorithm to find an {it Euclidean Shortest Path} from a source vertex $s$ to a sink vertex $t$ in the presence of obstacles in $Re^2$. Our algorithm takes $O(T+m(lg{m})(lg{n}))$ time and $O(n)$ space. Here, $O(T)$ is the time to triangulate the polygonal region, $m$ is the number of obstacles, and $n$ is the number of vertices. This bound is close to the known lower bound of $O(n+mlg{m})$ time and $O(n)$ space. Our approach involve progressing shortest path wavefront as in continuous Dijkstra-type method, and confining its expansion to regions of interest.
