New algorithm for computing shortest paths in weighted planar subdivisions

We present a practical new algorithm for the problem of computing low-cost paths in a weighted planar subdivision or on a weighted polyhedral surface. The algorithm is based on constructing a relatively sparse graph, a `pathnet', that links selected pairs of subdivision vertices (and `critical points of entry') with locally optimal paths. The pathnet can be searched for paths that are probably close to optimal and approach optimal, as one varies the parameter that controls the sparsity of the pathnet. We analyze our algorithm both analytically and experimentally. We report on the results of a set of experiments comparing the new algorithm with other standard methods.