Shortest rectilinear paths among weighted obstacles
D. T. Lee, T. H. Chen, C. D. Yang · 1990
In this paper we study 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. By using a graph-theoretical approach, we obtain two algorithms which run in Ο(nlog2 n) time and Ο(n log n) space and in Ο(n log3/2 n) time and space, respectively, where n is the number of the vertices of obstacles.