Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles
作者： S. Kapoor , S. N. Maheshwari
DOI: 10.1145/73393.73411
关键词: Distance 、 Widest path problem 、 Visibility graph 、 Shortest path problem 、 Mathematics 、 Euclidean shortest path 、 Combinatorics 、 Yen's algorithm 、 K shortest path routing 、 Shortest Path Faster Algorithm
摘要: The problem of determining the Euclidean shortest path between two points in presence m simple polygonal obstacles is studied. An O( m2 logn + nlogn ) algorithm developed, where n total number obstacles. A O(E+T) for visibility graph also shown, E edges and T time triangulating point set. This extended to a O(Es nlogn) Es bounded by m2.
acm.org
sci-hub.se 参考文章(6)
James A. Storer, John H. Reif, Shortest Paths in Euclidean Space with Polyhedral Obstacles. ,(1985)
Emo Welzl, Constructing the visibility graph for n-line segments in O(n2) time Information Processing Letters. ,vol. 20, pp. 167- 171 ,(1985) , 10.1016/0020-0190(85)90044-4
L. J. Guibas, J. Hershberger, Optimal shortest path queries in a simple polygon Proceedings of the third annual symposium on Computational geometry - SCG '87. pp. 50- 63 ,(1987) , 10.1145/41958.41964
D. T. Lee, F. P. Preparata, Euclidean shortest paths in the presence of rectilinear barriers Networks. ,vol. 14, pp. 393- 410 ,(1984) , 10.1002/NET.3230140304
Subir Kumar Ghosh, David M. Mount, An output sensitive algorithm for computing visibility graphs 28th Annual Symposium on Foundations of Computer Science (sfcs 1987). pp. 11- 19 ,(1987) , 10.1109/SFCS.1987.6
J. Hershberger, Finding the visibility graph of a simple polygon in time proportional to its size Proceedings of the third annual symposium on Computational geometry - SCG '87. pp. 11- 20 ,(1987) , 10.1145/41958.41960