Path simplification under difference area measure
Shervin Daneshpajouh, Alireza Zarei, Mohammad Ghodsi · 2009 14th International CSI Computer Conference · 2009
In this paper, we consider path simplification problem under difference area (diff-area) measure. Diff-area measure is defined as \Aa(Q) — Ab(Q)|, where Aa(Q) is the area under Q and above P and Ab(Q) is the area above Q and under P (see Figure 1). Böse et al [1] presented an approximation algorithm for finding a simplified path with at most k vertices that minimizes the diff-area measure which only works on x-monotone paths. The constraint of being x-monotone is restrictive in some applications like tracking bird migration paths or map boundary simplification. Here, we extend the method of Böse et al. [1] and present algorithms with the same time complexities as theirs for general paths.