Computing shortest paths in a polygonal do- main is a classic problem in computational geometry. Ecient algorithms for computing such paths use the continuous Dijk- stra paradigm [2], which not only allows one to nd the short- est path between two points but also computes the \shortest path map" from a given source|a structure enabling ecient queries of shortest paths to points in the domain.