On Optimal Min-# Curve Simplification Problem
share
In this paper we consider the classical min--# curve simplification problem in three different variants. Let δ>0, P be a polygonal curve with n vertices in R^d, and D(·,·) be a distance measure. We aim to simplify P by another polygonal curve P' with minimum number of vertices satisfying D(P,P') ≤δ. We obtain three main results for this problem: (1) An O(n^4)-time algorithm when D(P,P') is the Fréchet 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 ϵ>0, an O^*(n^2 n n)-time algorithm that computes P' whose vertices can lie anywhere in the space and whose Fréchet distance to P is at most (1+ϵ)δ 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/ϵ.
READ FULL TEXT