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 [AA(Q)-AB(Q)] is the area under Q and above P and AB(Q) is the area above Q and under P (see Figure 1 ) . Bose et al . [1] presented an approximation algorithm for finding a simplified path with at most K vertices that minimizes the diff - area measure whch only works on x - monotone paths . The constraint of being , - monotone is restrictive in some applications like tracking bird migration paths or map boundary simplification . Here , we extend the method of Bose et al . [1] and present algorithms with the same time complxities as theirs for general paths.