On simplifying dot maps

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.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2004-01
Language
ENG
Keywords

DISCREPANCY

Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.27, no.1, pp.43 - 62

ISSN
0925-7721
DOI
10.1016/j.comgeo.2003.07.005
URI
http://hdl.handle.net/10203/305
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
2002-038.pdf(693.93 kB)Download
  • Hit : 545
  • Download : 213
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 12 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0