COMPUTING SCIENCE

# Small-Town Story

# Latticeville

Something missing from all the models above is geography. There is no concept of distance; each town interacts with all the others on the same basis. On a real landscape, nearby towns are surely coupled more tightly than distant ones. A strong hint of spatial organization in the distribution of town sizes comes from the dramatic nighttime photographs of the Earth's surface made by the Defense Meteorological Satellite Program. The instrument that records these images is a sensitive photodetector meant to measure cloud cover by moonlight, but it can also record city lights. A study of the photographs done by Paul Sutton of the University of California, Santa Barbara and three colleagues failed to establish a precise calibration of pixel brightness to population density, but distinguishing large and small towns is easy.

In a satellite image of the upper Midwest and Great Plains, it's obvious that the scattering of towns and cities is anything but random. In some areas, strings of towns seem to radiate from major population centers. Elsewhere the pattern reflects the rectilinear network of roads, which in turn derives from the early surveys of the territory based on uniform square townships six miles on a side. Of course the lattice of towns is nowhere perfect, but there's enough regularity that it leaps to the eye.

There is more to the spatial distribution of towns than just the latticelike arrangement of sites. Each category of settlement—the hamlets, the villages, the towns, the cities, the conurbations—appears to have its own characteristic scale of distance. Progressing from smaller to larger settlements, the spacing increases. At the same time the lattice structure becomes less regular.

There's an easy hypothesis to account for the general features of this pattern, assuming that the siting of towns and cities is determined mainly by their role as service centers for a dispersed population. People want someplace nearby where they can mail a letter or pick up a quart of milk, but they are willing to travel farther for less-frequent errands, such as shopping for clothing, and they'll go farther still to buy a new car or see an art exhibit. Thus each category of settlement competes mainly with others of similar size, and the interstices between major centers can be filled in by smaller towns. Ecologists have observed a similar pattern in the distribution of desert plants, where the largest shrubs maintain a fixed distance from one another, determined by the size of the catchment basin needed to sustain their growth; smaller plants can survive in the open areas between the bigger bushes.

This biological analogy suggests one way to model the spatial distribution of towns: Let people be sprinkled over the landscape like rainfall and drain into the nearest basin; then each basin's radius of attraction grows along with its population. Another approach takes its inspiration from physics rather than biology. The geographic distribution of towns looks a little like the arrangement of atoms or molecules in a mildly disordered material, such as a glass. This observation suggests the metaphor of a repulsive potential between towns, as if there were springs holding them apart. From any starting configuration we can then allow the network of springs to relax to a state of lower total energy.

Yet there's something odd about this idea. In a model of a solid, the network of springs relaxes by adjusting the positions of the atoms. Towns and cities, however, seldom get up and move. Even if, say, Austin and Rochester, Minnesota, would both be better off if they were a few miles farther apart, there's no convenient way to slide them across the landscape. Instead, the towns stay put, and all adjustments have to be made by having people migrate from place to place.

Here is an algorithm (one of many possibilities) for constructing such a model. At each step, choose two towns at random with uniform probability. Calculate the repulsive interaction between each of these towns and all the other towns in the sample, using some sort of potential in which the repulsion increases with population and diminishes with distance. The sum of all these interactions can be interpreted as an energy. Now move a person from one town to the other in whichever direction lowers the overall energy. Then start over by choosing two new cities.

The details of the inter-town potential are where the model gets messy. An obvious starting point is "antigravity": The force between two towns is directly proportional to the product of their populations and inversely proportional to the square of their distance. (It is *anti*gravity because the force is repulsive rather than attractive.) Unfortunately, letting the system evolve under such a potential does not yield a realistic geography. The problem is that large cities not only repel one another but also strongly suppress the population of nearby smaller towns and villages, creating a vacant buffer zone that has no counterpart in the real world. A straightforward correction is to include another factor in the inter-town potential, namely the ratio of the smaller to the larger population. If this ratio is 1 (that is, the two towns have equal populations), then the repulsion will take its full strength. As the ratio approaches 0 (for the case of a one-stop-sign hamlet and a metropolis), the two places become almost oblivious of each other's presence.

The device of scaling the repulsive force according to the ratio of populations has a curious mathematical consequence. The force becomes proportional to *pq* x *p/q* (where *p* and *q* are the two populations, and *p* *q*). This expression immediately simplifies to *p*^{2}; that is, the larger population drops out of the calculation altogether, and the force between the towns depends only on the smaller population. Viewed in terms of a physical force law, this irrelevance of the larger population seems strange; it's certainly nothing like gravity. But it makes sense if we return to the original motivations for the model. We assumed that a hamlet can survive if and only if it is the closest place to buy milk or mail letters for everyone within a certain radius. Beyond that distance, it doesn't matter whether the next-nearest town is another tiny village or the city of Chicago.

A model constructed on these principles can be made to yield landscapes that visually have many of the same properties as real town-and-city distributions. A convenient starting configuration is a rectilinear grid of town sites, "jiggled" slightly to break the symmetries, with all the sites assigned the same starting population. Of course the towns never move; only their populations change as people transfer from site to site to reduce the energy of the system. After running the simulation for a few thousand steps per site, migration has altered the populations in such as way that villages, towns and cities are all distributed at the appropriate length scale. The smallest places are densely packed, whereas larger ones keep a greater distance between them.

It should be pointed out that this model is susceptible to the same demographic black-hole problem seen in the random-walk models. The lowest-energy state of the system is the configuration that packs everyone into a single city, since that eliminates all forces between towns. But the relaxation algorithm described above is unlikely ever to find this solution; it is a "greedy" algorithm that almost always becomes trapped in a metastable state. Here is a case where a "better" algorithm—one that converges to the true optimum—would not necessarily improve the model.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Computing Science**: Clarity in Climate Modeling

**Feature Article**: Candy Crush's Puzzling Mathematics

**Spotlight**: Briefings