  Cartograms are maps that rescale geographic regions (e.g., countries,
districts) such that their areas are proportional to quantitative demographic
data (e.g., population size, gross domestic product). Unlike conventional bar
or pie charts, cartograms can represent correctly which regions share common
borders, resulting in insightful visualizations that can be the basis for
further spatial statistical analysis. Computer programs can assist data
scientists in preparing cartograms, but developing an algorithm that can
quickly transform every coordinate on the map (including points that are not
exactly on a border) while generating recognizable images has remained a
challenge. Methods that translate the cartographic deformations into
physics-inspired equations of motion have become popular, but solving these
equations with sufficient accuracy can still take several minutes on current
hardware. Here we introduce a flow-based algorithm whose equations of motion
are numerically easier to solve compared with previous methods. The equations
allow straightforward parallelization so that the calculation takes only a few
seconds even for complex and detailed input. Despite the speedup, the proposed
algorithm still keeps the advantages of previous techniques: with comparable
quantitative measures of shape distortion, it accurately scales all areas,
correctly fits the regions together and generates a map projection for every
point. We demonstrate the use of our algorithm with applications to the 2016 US
election results, the gross domestic products of Indian states and Chinese
provinces, and the spatial distribution of deaths in the London borough of
Kensington and Chelsea between 2011 and 2014.

Computational Geometry