Loading...
Please wait, while we are loading the content...
Similar Documents
Area-Preserving Approximations of Polygonal Paths (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Cheong, Otfried Gudmundsson, Joachim Bose, Prosenjit Cabello, Sergio Speckmann, Bettina Kreveld, Marc Van |
| Abstract | 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. |
| File Format | |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Subject Keyword | Possible Number Additive Error Polygonal Path Max Wa X-monotone Polygonal Path Error Measure Edge Exists Let Wa Optimal Approximation Approximation Algorithm Nl Area-preserving Approximation |
| Content Type | Text |
