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.