论文标题
在本地Fréchet距离下的多线简化在2D中的运行时间几乎是季度的运行时
Polyline Simplification under the Local Fréchet Distance has Almost-Quadratic Runtime in 2D
论文作者
论文摘要
给定$ n $顶点的多线线，多线简化问题要求这些顶点的最小尺寸子序列定义了一个新的多线线，其与原始多线线的距离最多在某个距离下给定阈值，通常是本地的Hausdorff或本地的Fréchet距离。在这里，局部意味着，对于简化的多线线的每个线段，仅测量原始多线线中相应子曲线的距离。 Melkman和O'Rourke [计算形态'88]引入了几何数据结构，以在$ O（n^2 \ log n）$ time的本地Hausdorff距离下求解多线的简化，以及吉巴斯，Hershberger，Mitchell，Mitchell和Snoeyink [int。 J. Comput。地理。应用。 '93]考虑了在Fréchet距离下进行的多线简化，作为有序的刺伤，并提供了$ O（N^2 \ log^2 n）$的运行时间，但它们并没有限制简化的多线线以仅使用原始多线线的顶点。 我们表明，可以调整他们的技术以在$ O（n^2 \ log n）$ time中的本地fréchet距离下求解多线线，而不是$ o（n^3）$时，在应用IMAI-IRI-IRI算法时。我们的算法可以作为多种其他算法的更有效的子例程。我们提供了一个简单的算法描述以及严格的证明，以证实该定理。我们还研究了Melkman和O'Rourke引入的几何数据结构，我们将其称为Wavefront，更详细地说，并具有一些有趣的属性。结果，我们可以证明，在l $ _1 $和l $ _ \ infty $ norm下，算法可以显着简化，然后仅需要$ o（n^2）$的运行时间。我们还定义了一类天然的群，我们的算法总是在欧几里得Norm l $ _2 $中实现此运行时间。
Given a polyline on $n$ vertices, the polyline simplification problem asks for a minimum size subsequence of these vertices defining a new polyline whose distance to the original polyline is at most a given threshold under some distance measure, usually the local Hausdorff or the local Fréchet distance. Here, local means that, for each line segment of the simplified polyline, only the distance to the corresponding sub-curve in the original polyline is measured. Melkman and O'Rourke [Computational Morphology '88] introduced a geometric data structure to solve polyline simplification under the local Hausdorff distance in $O(n^2 \log n)$ time, and Guibas, Hershberger, Mitchell, and Snoeyink [Int. J. Comput. Geom. Appl. '93] considered polyline simplification under the Fréchet distance as ordered stabbing and provided an algorithm with a running time of $O(n^2 \log^2 n)$, but they did not restrict the simplified polyline to use only vertices of the original polyline. We show that their techniques can be adjusted to solve polyline simplification under the local Fréchet distance in $O(n^2 \log n)$ time instead of $O(n^3)$ when applying the Imai--Iri algorithm. Our algorithm may serve as a more efficient subroutine for multiple other algorithms. We provide a simple algorithm description as well as rigorous proofs to substantiate this theorem. We also investigate the geometric data structure introduced by Melkman and O'Rourke, which we refer to as wavefront, in more detail and feature some interesting properties. As a result, we can prove that under the L$_1$ and the L$_\infty$ norm, the algorithm can be significantly simplified and then only requires a running time of $O(n^2)$. We also define a natural class of polylines where our algorithm always achieves this running time also in the Euclidean norm L$_2$.
