×

Shortest rectilinear paths among weighted obstacles. (English) Zbl 0755.68137

The authors consider a problem of finding the shortest rectilinear path among weighted obstacles with rectilinear boundary. They allow the path to pass through the obstacles at extra cost. An algorithm which runs in \(O(n\log^ 2 n)\) time and \(O(n\log n)\) space is presented, where \(n\) is the total number of vertices of obstacles.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C35 Extremal problems in graph theory
68R10 Graph theory (including graph drawing) in computer science
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI