# Chip diffusion modeling yields better maps

PORTLAND, Ore. — Diffusion modeling similar to the technique used to design semiconductors has helped solve a long-standing problem in information display — the cartogram.

The classic example of a cartogram is a U.S. map with the size of each state proportional to its population. Computerized rendering of cartograms was invented at the University of Michigan in the 1960s, but the technique has since languished because even the fastest computers take an inordinate amount of time to render a well-drawn cartogram using traditional algorithms.

Using diffusion modeling, University of Michigan researcher Mark Newman solved the problem with almost instantaneous renderings of accurate, computerized cartograms. "We were working on a totally different problem — how to represent Internet traffic congestion. I was aware of diffusion models as a density-equalizing effect. That just happens to also be what the classic cartogram does — it equalizes the population density," said Newman, an assistant professor of physics.

Cartograms are made by modeling how populations would migrate if they were evenly distributed. Most are hand- drawn to maintain proper proportions such as keeping cities in the right states.

The original method of Waldo Tobler, one of the first scientists to develop computerized cartograms, used a vector average of the positions of corresponding corners and drew a new map with resulting distorted cells. Unfortunately, the algorithm takes a very long time to execute if a myriad of minor adjustments are made to maintain a legible map. To speed the process, many improvements have been proposed, including a continuous "displacement field" for each point on the map.

According to Newman, all these improvements to Tobler's original method have only made the algorithms more complex. This is where diffusion models entered the picture.

In chip design, diffusion describes the motion of atoms away from concentration gradients such as the diffusion of dopant atoms in semiconductors.

Diffusion models can also perform exactly the desired operations in cartograms because they simulate how atoms of one element spread out evenly. "We take areas where population is dense and model how it would diffuse from high-density areas into low-density areas, until the density is equalized everywhere," said Newman.

Besides applications like representing the size of states by their electoral votes, Newman said other areas of science require a quick method of making computerized cartograms. Mapping of census data, real-time election results or the geographic spread of illnesses like the flu are examples.