Min-Link Shortest Path Maps and Fréchet Distance

We present shortest path maps that support min-link queries from any source point on a line segment to destination points in either a simple polygon or a polygonal domain (a polygon with holes). These structures are more versatile than the traditional shortest path map from a fixed source point, and we use them to compute the min-link Fréchet distance between two polygonal curves. In addition to developing exact algorithms for min-link shortest path maps, the Fréchet distance, and the Hausdorff distance, we also present approximation algorithms that are accurate to within 1, 2, or 3 links of the optimal solution. The min-link Fréchet distance between polygonal curves inside a simple polygon interprets the boundary of the simple polygon as an obstacle. We prove that a free space cell (i.e., the parameter space representing all min-link distances between a pair of line segments) has the property that all min-link distances less than or equal to some threshold value ε define a free space that need not be convex but is always x-monotone, y-monotone, and connected. We use this property plus a novel additive B approximation for the Fréchet distance that runs in subquadratic O((kN/B) + (N2/B2)) time to compute the exact Fréchet distance in O(kN + N2) time. Here, N is the complexity of the polygonal curves, and k is the complexity of the simple polygon. Note that the exact runtime is asymptotically competitive with the O(N2 log N) runtime of the traditional (no obstacles) Fréchet distance [4]. For a polygonal domain, the monotonicity and connectedness properties no longer hold, so we use our shortest path map structure to represent a free space cell.