### Abstract

In this paper we consider the classical min--\# curve simplification problem in three different variants. Let $\delta>0$, $P$ be a polygonal curve with $n$ vertices in $\mathbb{R}^d$, and $D(\cdot,\cdot)$ be a distance measure. We aim to simplify $P$ by another polygonal curve $P'$ with minimum number of vertices satisfying $D(P,P') \leq \delta$. We obtain three main results for this problem: (1) An $O(n^4)$-time algorithm when $D(P,P')$ is the Fr\'echet distance and vertices in $P'$ are selected from a subsequence of vertices in $P$. (2) An NP-hardness result for the case that $D(P,P')$ is the directed Hausdorff distance from $P'$ to $P$ and the vertices of $P'$ can lie anywhere on $P$ while respecting the order of edges along $P$. (3) For any $\epsilon>0$, an $O^*(n^2\log n \log \log n)$-time algorithm that computes $P'$ whose vertices can lie anywhere in the space and whose Fr\'echet distance to $P$ is at most $(1+\epsilon)\delta$ with at most $2m+1$ links, where $m$ is the number of links in the optimal simplified curve and $O^*$ hides polynomial factors of $1/\epsilon$.

Original language | English |
---|---|

Article number | 1809.10269v1 |

Number of pages | 24 |

Journal | arXiv |

Publication status | Published - 26 Sep 2018 |

### Bibliographical note

24 pages, 9 figures### Keywords

- cs.CG
- F.2.2

## Fingerprint Dive into the research topics of 'On optimal min-# curve simplification problem'. Together they form a unique fingerprint.

## Cite this

Kerkhof, M. V. D., Kostitsyna, I., Löffler, M., Mirzanezhad, M., & Wenk, C. (2018). On optimal min-# curve simplification problem.

*arXiv*, [1809.10269v1].