摘要: This paper presents a simple O(n+k) time algorithm to compute the set of knon-crossing shortest paths between k source-destination pairs points on boundary polygon n vertices. Paths are allowed overlap but not cross in plane. A byproduct this result is an O(n) balanced geodesic triangulation which easy implement. The extends with one hole where may appear both inner and outer polygon. In latter case, goal collection non-crossing minimum total cost. case rectangular polygonal domain boundary12 briefly discussed.
sci-hub.se 参考文章(9)
Bernard Chazelle, A theorem on polygon cutting with applications 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). pp. 339- 349 ,(1982) , 10.1109/SFCS.1982.58
B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, J. Snoeyink, Ray shooting in polygons using geodesic triangulations Algorithmica. ,vol. 12, pp. 54- 68 ,(1994) , 10.1007/BF01377183
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
Leonidas J. Guibas, John Hershberger, Optimal shortest path queries in a simple polygon Journal of Computer and System Sciences. ,vol. 39, pp. 126- 152 ,(1989) , 10.1016/0022-0000(89)90041-X
John Hershberger, Jack Snoeyink, Computing minimum length paths of a given homotopy class Computational Geometry: Theory and Applications. ,vol. 4, pp. 63- 97 ,(1994) , 10.1016/0925-7721(94)90010-8
Jun-Ya Takahashi, Hitoshi Suzuki, Takao Nishizeki, Shortest Non-Crossing Rectilinear Paths in Plane Regions International Journal of Computational Geometry and Applications. ,vol. 7, pp. 419- 436 ,(1997) , 10.1142/S0218195997000259
Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert E. Tarjan, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons Algorithmica. ,vol. 2, pp. 209- 233 ,(1987) , 10.1007/BF01840360
Mark H. Overmars, Jan van Leeuwen, Maintenance of configurations in the plane Journal of Computer and System Sciences. ,vol. 23, pp. 166- 204 ,(1981) , 10.1016/0022-0000(81)90012-X
Junya Takahashi, Hitoshi Suzuki, Takao Nishizeki, Shortest noncrossing paths in plane graphs Algorithmica. ,vol. 16, pp. 339- 357 ,(1996) , 10.1007/BF01955681