Shortest curves in planar regions with curved boundary (Q1210291)

An algorithmic framework for shortest path problems in a ``curved world'' is developed and thoroughly discussed in detail. In particular two efficient algorithms are described. The first one is an output sensitive algorithm for the shortest path problem on simple plane polygons with possibly curved boundary. The time complexity is \(O(nk)\), where \(n\) is the number of polygon vertices and \(k\) is the number of vertices of the shortest path (curve). The second algorithm is the extension to multiply connected plane regions. The article is a valuable source of information on the state-of-the-art of curved computational geometry.