An Approximation Algorithm for Shortest Descending Paths

Details An Approximation Algorithm for Shortest Descending Paths An Approximation Algorithm for Shortest Descending Paths

2007-05-09

arxiv.org/abs/0705.1364v1

Computer Science

Computational Geometry

14 pages, 3 figures

Scientific paper

A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. No efficient algorithm is known to find a shortest descending path (SDP) from s to t in a polyhedral terrain. We give a simple approximation algorithm that solves the SDP problem on general terrains. Our algorithm discretizes the terrain with O(n^2 X / e) Steiner points so that after an O(n^2 X / e * log(n X /e))-time preprocessing phase for a given vertex s, we can determine a (1+e)-approximate SDP from s to any point v in O(n) time if v is either a vertex of the terrain or a Steiner point, and in O(n X /e) time otherwise. Here n is the size of the terrain, and X is a parameter of the geometry of the terrain.

Affiliated with

Also associated with

No associations

Rating

An Approximation Algorithm for Shortest Descending Paths 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 An Approximation Algorithm for Shortest Descending Paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Approximation Algorithm for Shortest Descending Paths will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-600109