Path simplification under difference area measure

In this paper, we consider path simplification problem under difference area (diff-area) measure. Diff-area measure is defined as |A_A(Q) - A_B(Q)|, where A_A(Q) is the area under Q and above P and A_B(Q) is the area above Q and under P (see Figure 1). Bo¿se et al 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 Bo¿se et al. and present algorithms with the same time complexities as theirs for general paths.