Area-preserving approximations of polygonal paths

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. ? 2005 Elsevier B.V. All rights reserved.
Publisher
Elsevier BV
Issue Date
2006-12
Language
ENG
Citation

JOURNAL OF DISCRETE ALGORITHMS, v.4, no.4, pp.554 - 566

ISSN
1570-8667
URI
http://hdl.handle.net/10203/315
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
pp942.pdf(181.86 kB)Download
  • Hit : 480
  • Download : 200
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0