Optimal BSPs and rectilinear cartograms

ABSTRACT

A cartogram is a thematic map that visualizes statistical data about a set of regions like countries, states or provinces. The size of a region in a cartogram corresponds to a particular geographic variable, for example, population. We present an algorithm for constructing rectilinear cartograms (each region is represented by a rectilinear polygon) with zero cartographic error and correct region adjacencies, and we test our algorithm on various data sets. It produces regions of very small complexity---in fact, most regions are rectangles---while still ensuring both exact areas and correct adjacencies for all regions.Our algorithm uses a novel subroutine that is interesting in its own right, namely a polynomial-time algorithm for computing optimal binary space partitions (BSPs) for rectilinear maps. This algorithm works for a general class of optimality criteria, including size and depth. We use this generality in our application to computing cartograms, where we apply a dedicated cost function leading to BSP's amenable to the constructing of high-quality cartograms.

REFERENCES

• 1: J. Bhasker and S. Sahni. A linear algorithm to check for the existence of a rectangular dual of a planar triangulated graph. Networks, 7:307--317, 1987.
• 2: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 3: Fabrizio d'Amore , Paolo Guilio Franciosa, On the optimal binary plane partition for sets of isothetic rectangles, Information Processing Letters, v.44 n.5, p.255-259, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90210-M]
• 4: M. de Berg, E. Mumford, and B. Speckmann. On rectilinear duals for vertex-weighted plane graphs. In Proc. 13th Intern. Symposium on Graph Drawing, number 3843 in LNCS, pages 61--72, 2005.
• 5: B. Dent. Cartography: Thematic Map Design. McGraw-Hill, 5th edition, 1999.
• 6: D. Dorling. Area Cartograms: their Use and Creation. Number 59 in Concepts and Techniques in Modern Geography. University of East Anglia, Environmental Publications, Norwich, 1996.
• 7: J. A. Dougenik, N. R. Chrisman, and D. R. Niemeyer. An algorithm to construct continuous area cartograms. The Professional Geographer, 37(1):75--81, 1985.
• 8: Herbert Edelsbrunner , Roman Waupotitsch, A combinatorial approach to cartograms, Computational Geometry: Theory and Applications, v.7 n.5-6, p.343-360, April 1997 [doi>10.1016/S0925-7721(96)00006-5]
• 9: M. Gastner and M. Newman. Diffusion-based method for producing density-equalizing maps. Proc. National Academy of Sciences of the United States of America, 101(20):7499--7504, 2004.
• 10: Roland Heilmann , Daniel A. Keim , Christian Panse , Mike Sips, RecMap: Rectangular Map Approximations, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.33-40, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.57]
• 11: Goos Kant , Xin He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Theoretical Computer Science, v.172 n.1-2, p.175-193, Feb. 10, 1997 [doi>10.1016/S0304-3975(95)00257-X]
• 12: Daniel A. Keim , Stephen C. North , Christian Panse, CartoDraw: A Fast Algorithm for Generating Contiguous Cartograms, IEEE Transactions on Visualization and Computer Graphics, v.10 n.1, p.95-110, January 2004 [doi>10.1109/TVCG.2004.1260761]
• 13: C. Kocmoud and D. House. A constraint-based approach to constructing continuous cartograms. In Proc. 8th Intern. Symposium on Spatial Data Handling, pages 236--246, 1998.
• 14: K. Koźmiàski and E. Kinnen. Rectangular dual of planar graphs. Networks, 5:145--157, 1985.
• 15: J. Olson. Noncontiguous area cartograms. Professional Geographer, 28:371--380, 1976.
• 16: E. Raisz. The rectangular statistical cartogram. Geographical Review, 24:292--296, 1934.
• 17: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 18: B. Speckmann, M. van Kreveld, and S. Florisson. A linear programming approach to rectangular cartograms. In Proc. 12th Intern. Symposium on Spatial Data Handling, pages 250--257, 2006.
• 19: W. Tobler. Pseudo-cartograms. The American Cartographer, 13:43--50, 1986.
• 20: M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, editors. Algorithmic Foundations of Geographic Information Systems. Springer, 1997.
• 21: M. van Kreveld and B. Speckmann. On rectangular cartograms. In Proc. 12th Europ. Symposium on Algorithms, number 3221 in LNCS, pages 724--735, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Experimentation

Keywords:
automated cartography, binary space partitions, cartograms, geometric algorithms, indexing structures