Computer Science – Computational Geometry
Scientific paper
2007-05-09
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.
Ahmed Mustaq
Lubiw Anna
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-600109