Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
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.
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
A. Grill, B.S. Meyerson, et al.
Proceedings of SPIE 1989
George Markowsky
J. Math. Anal. Appl.