摘要: Given a set of obstacles and two distinguished points in the plane problem finding collision-free path subject to certain optimization function is fundamental that arises many fields, such as motion planning robotics, wire routing VLSI logistics operations research. In this survey we emphasize its applications design limit ourselves rectilinear domain which goal be computed underlying are all rectilinearly oriented, i.e., segments either horizontal or vertical. We consider different environments, various criteria pertaining design, provide results have been developed past, present current give open problems for future
springer.com
sci-hub.st 参考文章(45)
D. T. Lee, T. H. Chen, C. D. Yang, Shortest rectilinear paths among weighted rectangles Journal of Information Processing. ,vol. 13, pp. 456- 462 ,(1991)
B. Chazelle, Triangulating a simple polygon in linear time foundations of computer science. pp. 220- 230 ,(1990) , 10.1109/FSCS.1990.89541
Cornell University. School of Operations Research and Industrial Engineering, Shortest Rectilinear Paths Among Obstacles Cornell University Operations Research and Industrial Engineering. ,(1987)
Mark Berg, Marc Kreveld, Bengt J. Nilsson, Mark H. Overmars, Finding Shortest Paths in the Presence of Orthogonal Obstacles Using a Combined L1 and Link Metric scandinavian workshop on algorithm theory. pp. 213- 224 ,(1990) , 10.1007/3-540-52846-6_91
Mikhail J. Atallah, Danny Z. Chen, Parallel rectilinear shortest paths with rectangular obstacles Computational Geometry: Theory and Applications. ,vol. 1, pp. 79- 113 ,(1991) , 10.1016/0925-7721(91)90002-V
K. Clarkson, S. Kapoor, P. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(logn)2) time Proceedings of the third annual symposium on Computational geometry - SCG '87. pp. 251- 257 ,(1987) , 10.1145/41958.41985
Takao Asano, Tetsuo Asano, Leonidas Guibas, John Hershberger, Hiroshi Imai, Visibility of disjoint polygons Algorithmica. ,vol. 1, pp. 49- 63 ,(1986) , 10.1007/BF01840436
Joseph S. B. Mitchell, Christos H. Papadimitriou, The weighted region problem: finding shortest paths through a weighted planar subdivision Journal of the ACM. ,vol. 38, pp. 18- 73 ,(1991) , 10.1145/102782.102784
P. J. de Rezende, D. T. Lee, Y. F. Wu, Rectilinear shortest paths in the presence of rectangular barriers Discrete & Computational Geometry. ,vol. 4, pp. 41- 53 ,(1989) , 10.1007/BF02187714
Subhash Suri, A linear time algorithm with minimum link paths inside a simple polygon Graphical Models \/graphical Models and Image Processing \/computer Vision, Graphics, and Image Processing. ,vol. 35, pp. 99- 110 ,(1986) , 10.1016/0734-189X(86)90127-1