Min-Link Shortest Path Maps and Fréchet Distance

Cook, Atlas F. IV
Wenk, Carola
Journal Title
Journal ISSN
Volume Title
UTSA Department of Computer Science

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.

Computer Science