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 flnd 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 ·
['Prosenjit Bose', 'Sergio Cabello', 'Otfried Cheong', 'Joachim Gudmundsson', 'Marc J. van Kreveld', 'Bettina Speckmann']
Area-preserving approximations of polygonal paths