J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
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 overlap 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 which 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 collection of non-crossing paths of minimum total cost. The case of a rectangular polygonal domain where source-destination pairs appear on the outer and one inner boundary12 is briefly discussed.
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
J. LaRue, C. Ting
Proceedings of SPIE 1989
I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics