摘要: Let p and q be two points in a simple polygon P. This chapter provides the Chazelle algorithm for computing ESP between that is contained It uses triangulation of polygons as presented previous preprocessing step, has time complexity determined by prior triangulation.
springer.com
sci-hub.st 参考文章(11)
Fajie Li, Reinhard Klette, Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm pacific-rim symposium on image and video technology. pp. 280- 291 ,(2006) , 10.1007/11949534_28
J.-R. Sack, J. Urrutia, Handbook of computational geometry North-Holland Publishing Co.. ,(2000)
Joseph S.B. Mitchell, Chapter 15 – Geometric Shortest Paths and Network Optimization Handbook of Computational Geometry. pp. 633- 701 ,(2000) , 10.1016/B978-044482537-7/50016-4
Fajie Li, Reinhard Klette, Decomposing a simple polygon into trapezoids computer analysis of images and patterns. pp. 726- 733 ,(2007) , 10.1007/978-3-540-74272-2_90
Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time Journal of the ACM. ,vol. 46, pp. 362- 394 ,(1999) , 10.1145/316542.316548
John Hershberger, A new data structure for shortest path queries in a simple polygon Information Processing Letters. ,vol. 38, pp. 231- 235 ,(1991) , 10.1016/0020-0190(91)90064-O
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
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
Bernard Chazelle, Triangulating a simple polygon in linear time Discrete & Computational Geometry. ,vol. 6, pp. 485- 524 ,(1991) , 10.1007/BF02574703