Name
Abstract | ||
|---|---|---|
the classic polyline simplification problem we want to replace a given polygonal curve $P$, consisting of $n$ vertices, by a subsequence $Pu0027$ of $k$ vertices from $P$ such that the polygonal curves $P$ and $Pu0027$ are as close as possible. Closeness is usually measured using the Hausdorff or Fru0027echet distance. These distance measures can be applied globally, i.e., to the whole curves $P$ and $Pu0027$, 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-Fru0027echet (in time $O(k n^5)$), and Local-Fru0027echet (in time $O(n^3)$). Our contribution is as follows. - Cubic time for all variants: For Global-Fru0027echet we design an algorithm running time $O(n^3)$. This shows that all three problems (Local-Hausdorff, Local-Fru0027echet, and Global-Fru0027echet) can be solved 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 high dimensions cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Fru0027echet, and Global-Fru0027echet). 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, high dimensions and over general $L_p$-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Fru0027echet, and Global-Fru0027echet, by providing new algorithms and conditional lower bounds. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.SoCG.2019.18 | symposium on computational geometry |
Field | DocType | Volume |
Discrete mathematics,Line segment,Combinatorics,Polygon,Vertex (geometry),Upper and lower bounds,Hausdorff space,Metric space,Subsequence,Polygonal chain,Mathematics | Journal | abs/1810.00621 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Karl Bringmann | 1 | 427 | 30.13 |
| Bhaskar Ray Chaudhury | 2 | 0 | 4.39 |