标题： 一个接近线性时间的精确算法，用于简单多边形边界上两条曲线之间的$L_1$-地真 Fréchet 距离 显示英文标题

标题： A near-linear time exact algorithm for the $L_1$-geodesic Fréchet distance between two curves on the boundary of a simple polygon

摘要： 设 $P$ 为一个具有 $k$ 个顶点的多边形。 设 $R$ 和 $B$ 是 $P$ 边界上的两条简单且内部不相交的曲线，分别具有 $n$ 和 $m$ 个顶点。 我们展示如何利用$L_1$- 距离在$P$中以$\mathcal{O}(k \log nm + (n+m) (\log^2 nm \log k + \log^4 nm))$时间计算$R$和$B$之间的 Fréchet 距离。 显示英文摘要

摘要： 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\'echet 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.