A polynomial time algorithm for finding an approximate shortest path amid weighted regions.
R. Inkulu, Sanjiv Kapoor · arXiv (Cornell University) · 2015
We devise a polynomial-time approximation scheme for the classical geometric problem of finding an approximate short path amid weighted regions. In this problem, a triangulated region P comprising of n vertices, a positive weight associated with each triangle, and two points s and t that belong to P are given as the input. The objective is to find a path whose cost is at most (1+\epsilon)OPT where OPT is the cost of an optimal path between s and t. Our algorithm initiates a discretized-Dijkstra wavefront from source s and progresses the wavefront till it strikes t. This result is about a cubic factor (in $n$) improvement over the Mitchell and Papadimitriou '91 result, which is the only known polynomial time algorithm for this problem to date.