On simplifying dot maps.

DOI10.1016/J.COMGEO.2003.07.005MaRDI QIDQ1421029zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Pat Morin, Mark de Berg, Otfried Cheong

Publication date 23 January 2004

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2003.07.005

zbMATH Keywords

\(\varepsilon\)-approximationsalgorithmdensity functiondiscrepancydot mapsnumerical examplesvisualization

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

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.

Recommendations

• Algorithms for ε-Approximations of Terrains
• Simplifying massive planar subdivisions
• Algorithmic aspects of proportional symbol maps
• Algorithmic Aspects of Proportional Symbol Maps
• Consistent thinning of large geographical data for map visualization

Cites work

• Algorithmics for hard problems.
• Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning
• Efficient and small representation of line arrangements with applications
• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• scientific article; zbMATH DE number 1182924 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• New Upper Bounds in Klee’s Measure Problem
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Translating a regular grid over a point set

Cited in

(3)

• scientific article; zbMATH DE number 5912556 (Why is no real title available?)
• Dense Glyph Sampling for Visualization
• scientific article; zbMATH DE number 1323022 (Why is no real title available?)

This page was built for publication: On simplifying dot maps.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1421029)