Item 10203/305
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | de Berg, M | ko |
| dc.contributor.author | Bose, P | ko |
| dc.contributor.author | Cheong, Otfried | ko |
| dc.contributor.author | Morin, P | ko |
| dc.date.accessioned | 2007-05-23T09:28:57Z | - |
| dc.date.available | 2007-05-23T09:28:57Z | - |
| dc.date.created | 2012-02-06 | - |
| dc.date.created | 2012-02-06 | - |
| dc.date.issued | 2004-01 | - |
| dc.identifier.citation | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.27, no.1, pp.43 - 62 | - |
| dc.identifier.issn | 0925-7721 | - |
| dc.identifier.uri | http://hdl.handle.net/10203/305 | - |
| dc.description.abstract | Dot maps-drawings of point sets-are a well known cartographic method to visualize density functions over an area. We study the problem of simplifying a given dot map: given a set P of points in the plane, we want to compute a smaller set Q of points whose distribution approximates the distribution of the original set P. We formalize this using the concept of epsilon-approximations, and we give efficient algorithms for computing the approximation error of a set Q of m points with respect to a set P of n points (with m less than or equal to n) for certain families of ranges, namely unit squares, arbitrary squares, and arbitrary rectangles. If the family R of ranges is the family of all possible unit squares, then we compute the approximation error of Q with respect to P in O(n log n) time. If R is the family of all possible rectangles, we present an O(mn log n) time algorithm. If R is the family of all possible squares, then we present a simple O(m(2)n + n log n) algorithm and an O(n(2)rootn-log n) time algorithm which is more efficient in the worst case. Finally, we develop heuristics to compute good approximations, and we evaluate our heuristics experimentally. (C) 2003 Elsevier B.V. All rights reserved. | - |
| dc.language | English | - |
| dc.language.iso | en | en |
| dc.publisher | ELSEVIER SCIENCE BV | - |
| dc.subject | DISCREPANCY | - |
| dc.type | Article | - |
| dc.identifier.wosid | 000187662600005 | - |
| dc.identifier.scopusid | 2-s2.0-84867962684 | - |
| dc.type.rims | ART | - |
| dc.citation.volume | 27 | - |
| dc.citation.issue | 1 | - |
| dc.citation.beginningpage | 43 | - |
| dc.citation.endingpage | 62 | - |
| dc.citation.publicationname | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | - |
| dc.identifier.doi | 10.1016/j.comgeo.2003.07.005 | - |
| dc.embargo.liftdate | 9999-12-31 | - |
| dc.embargo.terms | 9999-12-31 | - |
| dc.contributor.localauthor | Cheong, Otfried | - |
| dc.contributor.nonIdAuthor | de Berg, M | - |
| dc.contributor.nonIdAuthor | Bose, P | - |
| dc.contributor.nonIdAuthor | Morin, P | - |
| dc.type.journalArticle | Article; Proceedings Paper | - |
| dc.subject.keywordAuthor | dotmaps | - |
| dc.subject.keywordAuthor | discrepancy | - |
| dc.subject.keywordAuthor | epsilon-approximations | - |
| dc.subject.keywordPlus | DISCREPANCY | - |
- Appears in Collection
- CS-Journal Papers(저널논문)
- Files in This Item
This item is cited by other documents in WoS
| ⊙ Detail Information in WoSⓡ | Click to see |  |
| ⊙ Cited 22 items in WoS | Click to see citing articles in |  |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.