Geodesic Fréchet and Hausdorff Distance Inside a Simple Polygon

We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fréchet optimization problems in the plane. This randomized approach is based on a variant of red-blue intersections and is appealing due to its elegance and practical efficiency when compared to parametric search.

The frontiers of knowledge are expanded by our debut of the first algorithm for the geodesic Fréchet decision problem between two polygonal curves A and B inside a simple bounding polygon P. The geodesic decision problem is asymptotically almost as fast as its non-geodesic sibling and requires O(N2 log k) time and O(k + N) space after O(k) preprocessing, where N is the larger of the complexities of A and B and k is the complexity of P. The culmination of our work is a randomized solution to the geodesic Fréchet optimization problem that runs in O(k + (N2 log kN) log N) expected time and O(k +N2) space. This run time is within a logarithmic factor of being asymptotically equivalent to the run time of the non-geodesic Fréchet optimization problem [3].

The algorithm for the geodesic Fréchet decision problem rests on a foundation of several key properties. We prove that a geodesic cell for polygonal curves inside a simple polygon P has at most one free region and that this region is monotone. This allows reachability information to be propagated through a cell in constant time once its boundaries are known. We also show how to compute a cell's boundaries in O(log k) time after preprocessing P in O(k) time and space.

Other interesting and related results are that the geodesic Hausdorff distance between point sets inside a simple polygon P can be computed in O((k + N) log(k + N)) time and O(k + N) space. The approach relies on geodesic Voronoi diagrams and geodesic distance queries inside P. The geodesic Hausdorff distance for line segments inside P can be found in O(k + N2 log k) time and O(k + N) space.