Can I read Polyline Simplification has Cubic Complexity on EtoBox?

Polyline Simplification has Cubic Complexity by Bringmann, Karl; Chaudhury, Bhaskar Ray is a scholarly article available to read on EtoBox.

What is Polyline Simplification has Cubic Complexity about?

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 h

Author

Bringmann, Karl; Chaudhury, Bhaskar Ray

Published

2018

Language

EN