Approximate Euclidean shortest paths amid convex obstacles.
Pankaj K. AgarwalR. SharathkumarHai YuPublished in: SODA (2009)
Keyphrases
- shortest path
- piecewise linear
- shortest path problem
- road network
- shortest path algorithm
- weighted graph
- geodesic distance
- optimal path
- euclidean distance
- travel time
- shortest distance
- path length
- euclidean space
- convex hull
- minimal surface
- flow graph
- minimum cost flow
- social networks
- strongly connected components
- wireless sensor networks