On simplifying dot maps. (Q1421029)

Dot maps are a known method to visualize density functions over an area.. Given a set \(P\) in the plane, the authors want to compute a smaller set \(Q\) of points whose distribution approximates the distribution of the set \(P\). The known concept of \(\varepsilon\)-approximations is used for a formal approach. Efficient algorithms for computing the approximation error of a set \(Q\) of \(m\) points with respect to a set \(P\) of more points for certain families of ranges, namely unit squares, arbitrary squares, and arbitrary rectangles are presented. For instance, if the family of ranges is the family of all possible unit squares, then it is possible to compute the approximation error of \(Q\) with respect to \(P\) in \(O(\log n)\) time. For the family of all possible rectangles an \(O(mn\log n)\)-time-algorithmus is given. The paper contains some experimental results about the evaluation of some heuristics for good approximations given in the last chapter. An open problem is the following: The authors suspect that computing the best approximation of a given size with respect to a given set \(P\) is \(NP\)-hard . Further the problem of giving some points of the set \(P\) a higher weight for a bigger chance to be present in \(Q\) is discussed.