k-pairs non-crossing shortest paths in a simple polygon

This paper presents a simple O(n + k) time algorithm to compute the set of k non crossing shortest paths between k source-destination pairs of points on the boundary of a simple polygon of n vertices. Paths are allowed to ove rlap but are not allowed to cross in the plane. A byproduct of this result is an O(n) time algorithm to compute a balanced geodesic triangulation whic h is easy to implement. The algorithm extends to a simple polygon with one hole where source-destination pairs may appear on both the inner and outer boundary of the polygon. In the latter case, the goal is to compute a colle ction of non-crossing paths of minimum total cost. The case of a rectangula r polygonal domain where source-destination pairs appear on the outer and o ne inner boundary(12) is briefly discussed.