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 mn) 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(nlogn) time. If R is the family of all possible rectangles, we present an O(mnlogn) time algorithm. If R is the family of all possible squares, then we present a simple O(m 2n+nlogn) algorithm and an O(n 2 nlogn) time algorithm which is more efficient in the worst case. Finally, we develop heuristics to compute good approximations, and we evaluate our heuristics experimentally.

Additional Metadata
Keywords ε-approximations, Discrepancy, Dotmaps
Persistent URL
Journal Computational Geometry
De Berg, M. (Mark), Bose, P, Cheong, O. (Otfried), & Morin, P. (2004). On simplifying dot maps. Computational Geometry, 27(1), 43–62. doi:10.1016/j.comgeo.2003.07.005