20061201
Areapreserving approximations of polygonal paths
Publication
Publication
Journal of Discrete Algorithms , Volume 4  Issue 4 p. 554 566
Let P be an xmonotone 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 NPhard 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 NPhard 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.
Additional Metadata  

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