Shortest Rectilinear Paths among Weighted Rectangles

We consider the problem of a rectilinear shortest path among weighted obstacles. Instead of restricting a path to avoid obstacles totally, we allow it 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 disjoint, weighted rectangles. By using a plane sweep approach and a data structure called the weighted segment tree, we obtain an algorithm that runs in optimalθ(n log n) time andθ(n) space, where n is the number of rectangles.