A near optimal algorithm for finding Euclidean shortest path in polygonal domain

Rajasekhar Inkulu, Sanjiv Kapoor, S. N. 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(\…