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

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

2010-11-30

arxiv.org/abs/1011.6481v1

Computer Science

Computational Geometry

50 pages

Scientific paper

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+m\lg{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.

Affiliated with

Also associated with

No associations

Rating

A near optimal algorithm for finding Euclidean shortest path in polygonal domain does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A near optimal algorithm for finding Euclidean shortest path in polygonal domain, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A near optimal algorithm for finding Euclidean shortest path in polygonal domain will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444877