Area-preserving approximations of polygonal paths

P. Bose, S. Cabello, O. Cheong, J. Gudmundsson, M.J. Kreveld, van, B. Speckmann

Research output: Contribution to journalArticleAcademicpeer-review

28 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)554-566
JournalJournal of Discrete Algorithms
Issue number4
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Area-preserving approximations of polygonal paths'. Together they form a unique fingerprint.

  • Cite this

    Bose, P., Cabello, S., Cheong, O., Gudmundsson, J., Kreveld, van, M. J., & Speckmann, B. (2006). Area-preserving approximations of polygonal paths. Journal of Discrete Algorithms, 4(4), 554-566.