Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
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.
Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985
Jianke Yang, Robin Walters, et al.
ICML 2023
Yi Zhou, Parikshit Ram, et al.
ICLR 2023