# On optimal min-# curve simplification problem

Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, Carola Wenk

### 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 1809.10269v1 24 arXiv Published - 26 Sep 2018

### Bibliographical note

24 pages, 9 figures

• cs.CG
• F.2.2

• ## 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].