SHORTEST CURVES IN PLANAR REGIONS WITH CURVED BOUNDARY

A general framework is presented for describing shortest curve algorit hms and their time complexity in regions of the plane whose boundaries may be curved. An algorithm that accepts curved boundary Jordan regio ns along with given start and end points and produces the shortest cur ve between them is presented. Its time complexity is bounded by the pr oduct of the complexity of the region's boundary and that of the outpu t shortest curve. (When the region is a simple polygon with N vertices , the time bound is O(Nk), where k is the number of vertices in the sh ortest curve.) A second algorithm produces shortest curves in multiply connected regions with possibly curved boundary.