A Near-Linear Time Exact Algorithm for the L1-Geodesic Fréchet Distance Between Two Curves on the Boundary of a Simple Polygon

Abstract

Let P be a polygon with k vertices. Let R and B be two simple, interior disjoint curves on the boundary of P, with n and m vertices. We show how to compute the Fréchet distance between R and B using the geodesic L1-distance in P in O(klog nm + (n + m)(log2 nmlog k + log4 nm)) time.