In this paper we propose two linear time algorithms for computing the shortest path tree rooted at any vertex of a weak visibility polygon. The first algorithm computes the shortest path tree in a polygon weakly visible from a given internal segment. The second algorithm computes the shortest path tree in a weak visibility polygon without the knowledge of a visibility segment. In both algorithms we use the convexity property of shortest paths in weak visibility polygons established in [4,11].

Additional Metadata
Series Lecture Notes in Computer Science
Citation
Ghosh, S.K. (Subir Kumar), Maheshwari, A, Pal, S.P. (Sudebkumar Prasant), Saluja, S. (Sanjeev), & Veni Madhavan, C.E. (C. E.). (1991). Computing the shortest path tree in a weak visibility polygon. In Lecture Notes in Computer Science.