Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA (Q) be the area above P and below Q, and let 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). 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) ≤ 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)} ≤ 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. Nevertheless, in this error measure we provide an algorithm for computing an optimal approximation up to an additive error.

Journal of Discrete Algorithms
School of Computer Science

Bose, P, Cabello, S. (Sergio), Cheong, O. (Otfried), Gudmundsson, J. (Joachim), van Kreveld, M. (Marc), & Speckmann, B. (Bettina). (2006). Area-preserving approximations of polygonal paths. Journal of Discrete Algorithms, 4(4), 554–566. doi:10.1016/j.jda.2005.06.008