A new algorithm for computing shortest paths in weighted planar subdivisions (extended abstract)
Christian S. Mata, Joseph S. B. Mitchell · 1997
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 baaed 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 pat hs that are provably 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.The weighted region problem models the minimum-time path problem for a point robot moving in a terrain of varied