DC Field | Value | Language |
---|---|---|
dc.contributor.author | Bose P. | ko |
dc.contributor.author | Cabello S. | ko |
dc.contributor.author | Cheong, Otfried | ko |
dc.contributor.author | Gudmundsson J. | ko |
dc.contributor.author | van Kreveld M. | ko |
dc.contributor.author | Speckmann B. | ko |
dc.date.accessioned | 2007-05-25 | - |
dc.date.available | 2007-05-25 | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 2006-12 | - |
dc.identifier.citation | JOURNAL OF DISCRETE ALGORITHMS, v.4, no.4, pp.554 - 566 | - |
dc.identifier.issn | 1570-8667 | - |
dc.identifier.uri | http://hdl.handle.net/10203/315 | - |
dc.description.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. ? 2005 Elsevier B.V. All rights reserved. | - |
dc.description.sponsorship | P.B. is partially supported by the Natural Science and Engineering Research Council of Canada, J.G. is partially supported by the Netherlands Organisation for Scientific Research, and S.C. is partially supported by the European Community Sixth Framework Programme under a Marie Curie Intra-European Fellowship. NICTA is funded by the Australian Government's Backing Australia's Ability initiative, in part through the Australian Research Council. | en |
dc.language | English | - |
dc.language.iso | en | en |
dc.publisher | Elsevier BV | - |
dc.title | Area-preserving approximations of polygonal paths | - |
dc.type | Article | - |
dc.identifier.scopusid | 2-s2.0-33750629507 | - |
dc.type.rims | ART | - |
dc.citation.volume | 4 | - |
dc.citation.issue | 4 | - |
dc.citation.beginningpage | 554 | - |
dc.citation.endingpage | 566 | - |
dc.citation.publicationname | JOURNAL OF DISCRETE ALGORITHMS | - |
dc.embargo.liftdate | 9999-12-31 | - |
dc.embargo.terms | 9999-12-31 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | Bose P. | - |
dc.contributor.nonIdAuthor | Cabello S. | - |
dc.contributor.nonIdAuthor | Gudmundsson J. | - |
dc.contributor.nonIdAuthor | van Kreveld M. | - |
dc.contributor.nonIdAuthor | Speckmann B. | - |
dc.subject.keywordAuthor | Approximating algorithm | - |
dc.subject.keywordAuthor | Polygonal line simplification | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.