Approximation Algorithms for Shortest Descending Paths in Terrains

Simple item page
dc.creatorAhmed, Mustaq
dc.creatorDas, Sandip
dc.creatorLodha, Sachin
dc.creatorLubiw, Anna
dc.creatorMaheshwari, Anil
dc.creatorRoy, Sasanka
dc.date2008-05-09
dc.date.accessioned2026-07-07T09:38:04Z
dc.date.available2026-07-07T09:38:04Z
dc.descriptionA 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.
dc.description24 pages, 8 figures
dc.identifierhttps://arxiv.org/abs/0805.1401
dc.identifierhttp://arxiv.org/abs/0805.1401
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/160677
dc.subjectComputational Geometry
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titleApproximation Algorithms for Shortest Descending Paths in Terrains
dc.typetext

Files

Collections

arXiv