TY - JOUR
T1 - Area-preserving approximations of polygonal paths
AU - Bose, P.
AU - Cabello, S.
AU - Cheong, O.
AU - Gudmundsson, J.
AU - Kreveld, van, M.J.
AU - Speckmann, B.
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
U2 - 10.1016/j.jda.2005.06.008
DO - 10.1016/j.jda.2005.06.008
M3 - Article
VL - 4
SP - 554
EP - 566
JO - Journal of Discrete Algorithms
JF - Journal of Discrete Algorithms
SN - 1570-8667
IS - 4
ER -