Approximation Algorithms for Shortest Descending Paths in Terrains

Details Approximation Algorithms for Shortest Descending Paths in Terrains Approximation Algorithms for Shortest Descending Paths in Terrains

2008-05-09

arxiv.org/abs/0805.1401v1

Computer Science

Computational Geometry

24 pages, 8 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 two approximation algorithms (more precisely, FPTASs) that solve the SDP problem on general terrains. Both algorithms are simple, robust and easy to implement.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-332768