A fast,free-form rubber-sheet algorithm for contiguous area cartograms

This article presents a fast, free-form rubber-sheet (Carto3F) algorithm for the construction of contiguous area cartograms. Rubber-sheet algorithms are influential and popular because of their conceptual simplicity. Existing rubber-sheet algorithms, however, tend to be algorithmically inefficient and computationally slow. More critically, they cannot completely preserve topology. Carto3F specifically improves rubber-sheet algorithms in these two aspects. First, with a spatial structure of quadtree and a mathematical condition for topological equivalence, Carto3F can prevent topological errors and guarantees topological integrity. Second, Carto3F is designed with efficiency as a priority. Its efficiency is primarily gained through using the auxiliary quadtree to reduce the number of points to be transformed. Furthermore, Carto3F allows parallel computation and can fully take advantage of the increasingly common multi-core, multi-thread processors. Based on the mathematical analysis, Carto3F also mitigates the effect of force cancellation that is inherent in rubber-sheet algorithms. On a computer equipped with a 2.4-GHz quad-core CPU, Carto3F can produce quality population cartograms of the United States, China, and the world within 1 second, 18 seconds, and 8 minutes, respectively. Quantitative measures show that Carto3F outperforms the optimized rubber-sheet algorithm and the diffusion algorithm in both transformation effectiveness and computational efficiency.