Lee, D. T.; Yang, C. D.; Chen, T. H. Shortest rectilinear paths among weighted obstacles. (English) Zbl 0755.68137 Int. J. Comput. Geom. Appl. 1, No. 2, 109-124 (1991). 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. Reviewer: P.Horak (Bratislava) Cited in 13 Documents 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 Keywords:shortest path; weighted obstacle; rectilinear path PDFBibTeX XMLCite \textit{D. T. Lee} et al., Int. J. Comput. Geom. Appl. 1, No. 2, 109--124 (1991; Zbl 0755.68137) Full Text: DOI