Geodesic Fréchet Distance with Polygonal Obstacles

We present the first algorithm to compute the geodesic Fréchet distance between two polygonal curves in a plane with polygonal obstacles, where distances between points are measured as the length of a shortest path between them. Using shortest path structures that we call dynamic and static spotlights, we efficiently construct and propagate reachability information through the free space diagram to solve the Fréchet distance. We also show how to construct a novel shortest path map from a line segment source (instead of from a point source). This shortest path map supports geodesic distance queries from any point s ∈ ab to any point t ∈ cd in optimal logarithmic time and permits the shortest path to be reported in output-sensitive fashion.