Approximate Shortest Path through a Weighted Planar Subdivision

This paper presents an approximation algorithm for finding a shortest path between two points $s$ and $t$ in a weighted planar subdivision $\text{PS}$. Each face $f$ of $\text{PS}$ is associated with a weight $w_f$, and the cost of travel along a line segment on $f$ is $w_f$ multiplied by the Euclidean norm of that line segment. The cost of a path which traverses across several faces of the subdivision is the sum of the costs of travel along each face. Our algorithm progreeses the discretized shortest path wavefront from source $s$, and takes polynomial time in finding an $ϵ$-approximate shortest path.