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

RouteProblem:Let P be a polygonal room, possibly with "holes" (obstacles), having n vertices.The problem of computing a shortest tour in order that a mobile guard can "see" all of T is known as the Watchman Route Problem (WRP).If P is a simple polygon (having no holes), then WRP can be solved exactly, in time 0(n4) [7, 23].However, WRP is known to be NP-hard if ~has holes (a simple reduction from Euclidean TSP; see [8]), even if T is rectilinear.But, as with RBSP, no approximation algorithms have previously been found for this problem.We give an O(log m) approximation algorithm for the WRP when the polygon T is rectilinear, where m < n is the minimum number of edges in a shortest rectilinear watchman route.