Article

Optimal BSPs and rectilinear cartograms

Authors:

Bettina SpeckmannAuthors Info & Claims

GIS '06: Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems

Pages 19 - 26

https://doi.org/10.1145/1183471.1183476

Published: 10 November 2006 Publication History

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]

T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2nd edition, 2001.

Digital Library

[3]

F. d'Amore and P. G. Franciosa. On the optimal binary plane partition for sets of isothetic rectangles. Information Processing Letters, 44(5):255--259, 1992.

Digital Library

[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.

Digital Library

[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]

H. Edelsbrunner and E. Waupotitsch. A combinatorial approach to cartograms. Computational Geometry: Theory and Applications, 7:343--360, 1997.

Digital Library

[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]

R. Heilmann, D. A. Keim, C. Panse, and M. Sips. Recmap: Rectangular map approximations. In Proc. IEEE Symposium on Information Visualization, pages 33--40, 2004.

Digital Library

[11]

G. Kant and X. He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science, 172:175--193, 1997.

Digital Library

[12]

D. Keim, S. North, and C. Panse. Cartodraw: A fast algorithm for generating contiguous cartograms. IEEE Transactions on Visualization and Computer Graphics, 10:95--110, 2004.

Digital Library

[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]

H. Samet, editor. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989.

Digital Library

[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.

Cited By

KAYA MYILMAZ İ(2021)Kartogram Haritaların Nüfus Analizinde KullanımıAfyon Kocatepe University Journal of Sciences and Engineering10.35414/akufemubid.97725121:5(1108-1124)Online publication date: 31-Oct-2021
https://doi.org/10.35414/akufemubid.977251
Biedl TVelázquez L(2011)Orthogonal cartograms with few corners per faceProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033199(98-109)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.5555/2033190.2033199
Di Battista GSquarcella CNagele W(2011)How to visualize the k-root name server (demo)Proceedings of the 19th international conference on Graph Drawing10.1007/978-3-642-25878-7_19(191-202)Online publication date: 21-Sep-2011
https://dl.acm.org/doi/10.1007/978-3-642-25878-7_19
Show More Cited By

Index Terms

Optimal BSPs and rectilinear cartograms
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Computing cartograms with optimal complexity
SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal ...
Computing Cartograms with Optimal Complexity

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal ...
Cartograms, Self-Organizing Maps, and Magnification Control
WSOM '09: Proceedings of the 7th International Workshop on Advances in Self-Organizing Maps

This paper presents a simple way to compensate the magnification effect of Self-Organizing Maps (SOM) when creating cartograms using Carto-SOM. It starts with a brief explanation of what a cartogram is, how it can be used, and what sort of metrics can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GIS '06: Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems

November 2006

264 pages

ISBN:1595935290

DOI:10.1145/1183471

General Chairs:
Rolf A. de By
ITC, The Netherlands
,
Silvia Nittel
University of Maine, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM06

Sponsor:

CIKM06: Conference on Information and Knowledge Management

November 10 - 11, 2006

Virginia, Arlington, USA

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
320
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

KAYA MYILMAZ İ(2021)Kartogram Haritaların Nüfus Analizinde KullanımıAfyon Kocatepe University Journal of Sciences and Engineering10.35414/akufemubid.97725121:5(1108-1124)Online publication date: 31-Oct-2021
https://doi.org/10.35414/akufemubid.977251
Biedl TVelázquez L(2011)Orthogonal cartograms with few corners per faceProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033199(98-109)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.5555/2033190.2033199
Di Battista GSquarcella CNagele W(2011)How to visualize the k-root name server (demo)Proceedings of the 19th international conference on Graph Drawing10.1007/978-3-642-25878-7_19(191-202)Online publication date: 21-Sep-2011
https://dl.acm.org/doi/10.1007/978-3-642-25878-7_19
de Berg MKhosravi A(2010)Optimal binary space partitions in the planeProceedings of the 16th annual international conference on Computing and combinatorics10.5555/1886811.1886842(216-225)Online publication date: 19-Jul-2010
https://dl.acm.org/doi/10.5555/1886811.1886842
de Berg MKhosravi A(2010)Optimal Binary Space Partitions in the PlaneComputing and Combinatorics10.1007/978-3-642-14031-0_25(216-225)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14031-0_25
De Berg MMumford ESpeckmann B(2009)On rectilinear duals for vertex-weighted plane graphsDiscrete Mathematics10.1016/j.disc.2007.12.087309:7(1794-1812)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1016/j.disc.2007.12.087
Rahman MMiura KNishizeki T(2009)Octagonal drawings of plane graphs with prescribed face areasComputational Geometry: Theory and Applications10.1016/j.comgeo.2008.09.00242:3(214-230)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1016/j.comgeo.2008.09.002

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents