Optimal BSPs and rectilinear cartograms

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationProceedings 14th International Symposium on Advances in Geographic Information Systems (ACM-GIS'06, Arlington VA, USA, November 10-11, 2006)
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
ISBN (Print)1-59593-529-0
Publication statusPublished - 2006


Dive into the research topics of 'Optimal BSPs and rectilinear cartograms'. Together they form a unique fingerprint.

Cite this