Polyline Simplification has Cubic Complexity
Polyline Simplification has Cubic Complexity
复制标题
折线简化具有三次复杂性
DOI：
10.4230/lipics.socg.2019.18
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
B. Chaudhury
中科院分区：
文献类型：
--
作者：
K. Bringmann;B. Chaudhury
在经典的三角形简化问题中，我们想用一个由$n$个顶点组成的给定的多边形曲线$P$，由$P$的$k$个顶点组成的子序列$P '$，使得多边形曲线$P$和$P'$尽可能地接近。接近度通常使用Hausdorff或Fr\'echet距离来测量。这些距离测量可以“全局地”应用，即，到整个曲线$P$和$P '$，或“局部地”，即，每个简化的子曲线和线段，它被单独替换（然后取最大值）。这就产生了四个问题变体：全局-豪斯多夫（已知是NP难的），局部-豪斯多夫（时间为O（n^3）$），全局-Fr\'echet（时间为O（k n^5）$）和局部-Fr\' echet（时间为O（n^3）$）。
我们的贡献如下。
- 算法复杂度为O（n^3），时间复杂度为O（n^3）。这表明，所有三个问题（Local-Hausdorff，Local-Fr\'echet和Global-Fr\' echet）都可以在立方时间内解决。所有这些算法都适用于一般的度量空间，例如$（\mathbb{R}^d，L_p）$，但隐藏常数依赖于$p$和（线性）$d$。
- 三次条件下界：我们提供的证据表明，在高维立方时间基本上是最佳的所有三个问题（本地-豪斯多夫，本地-Fr\'echet，和全球-Fr\' echet）。具体地说，对于$（\mathbb{R}^d，L_p）$（$p = 1$）的简化，将立方时间提高到$O（n^{3-\displaystyle\texttrm {poly}（d））$将违反合理的假设。对于所有的p \in [1，\infty），p \ne 2$，我们得到了类似的结果.
总的来说，在高维和一般的$L_p$-规范，我们解决的复杂性，相对于本地Hausdorff，本地Fr\'echet，和全球Fr\' echet，通过提供新的算法和条件下界。
In the classic polyline simplification problem we want to replace a given polygonal curve $P$, consisting of $n$ vertices, by a subsequence $P'$ of $k$ vertices from $P$ such that the polygonal curves $P$ and $P'$ are as close as possible. Closeness is usually measured using the Hausdorff or Fr\'echet distance. These distance measures can be applied "globally", i.e., to the whole curves $P$ and $P'$, or "locally", i.e., to each simplified subcurve and the line segment that it was replaced with separately (and then taking the maximum). This gives rise to four problem variants: Global-Hausdorff (known to be NP-hard), Local-Hausdorff (in time $O(n^3)$), Global-Fr\'echet (in time $O(k n^5)$), and Local-Fr\'echet (in time $O(n^3)$).
Our contribution is as follows.
- Cubic time for all variants: For Global-Fr\'echet we design an algorithm running in time $O(n^3)$. This shows that all three problems (Local-Hausdorff, Local-Fr\'echet, and Global-Fr\'echet) can be solved in cubic time. All these algorithms work over a general metric space such as $(\mathbb{R}^d,L_p)$, but the hidden constant depends on $p$ and (linearly) on $d$.
- Cubic conditional lower bound: We provide evidence that in high dimensions cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Fr\'echet, and Global-Fr\'echet). Specifically, improving the cubic time to $O(n^{3-\epsilon} \textrm{poly}(d))$ for polyline simplification over $(\mathbb{R}^d,L_p)$ for $p = 1$ would violate plausible conjectures. We obtain similar results for all $p \in [1,\infty), p \ne 2$.
In total, in high dimensions and over general $L_p$-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Fr\'echet, and Global-Fr\'echet, by providing new algorithms and conditional lower bounds.