1991
Computing the shortest path tree in a weak visibility polygon
Publication
Publication
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 | |
---|---|
Lecture Notes in Computer Science | |
Organisation | Computational Geometry Lab |
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.
|