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 ε-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 ≤ 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~2n + n log n) algorithm and an O(n~2 n~(1/2) 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.