SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE
D. T. Lee, C. D. Yang, T. H. Chen · International Journal of Computational Geometry & Applications · 1991
We consider a rectilinear shortest path problem among weighted obstacles. Instead of restricting a path to totally avoid obstacles we allow a path to pass through them at extra costs. The extra costs are represented by the weights of the obstacles. We aim to find a shortest rectilinear path between two distinguished points among a set of weighted obstacles. The unweighted case is a special case of this problem when the weight of each obstacle is +∞. By using a graph-theoretical approach, we obtain two algorithms which run in O(n log 2 n) time and O(n log n) space and in O(n log 3/2 n) time and space, respectively, where n is the number of the vertices of the obstacles.