A near-linear time exact algorithm for the $L_1$-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 $L_1$-distance in $P$ in $\mathcal{O}(k\log nm+(n+m)({\log }^{2}nm\log k+{\log }^{4}nm))$ time.

19 pages, 5 figures