Area-preserving approximations of polygonal paths

Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P   let WA(Q)WA(Q) be the area above P and below Q  , and let WB(Q)WB(Q) be the area above Q and below P. Given P and an integer k, we show how to compute a path Q with at most k   edges that minimizes WA(Q)+WB(Q)WA(Q)+WB(Q). Given P and a cost C, we show how to find a path Q   with the smallest possible number of edges such that WA(Q)+WB(Q)⩽CWA(Q)+WB(Q)⩽C. However, given P, an integer k, and a cost C, it is NP-hard to determine if a path Q with at most k   edges exists such that max{WA(Q),WB(Q)}⩽Cmax{WA(Q),WB(Q)}⩽C. We describe an approximation algorithm for this setting. Finally, it is also NP-hard to decide whether a path Q   exists such that |WA(Q)−WB(Q)|=0|WA(Q)−WB(Q)|=0. Nevertheless, in this error measure we provide an algorithm for computing an optimal approximation up to an additive error.