MY AMERICAN SCIENTIST
SEARCH

COMPUTING SCIENCE

# Long Division

However tricky the divide problem may prove to be, a correct algorithm surely does exist, since nature somehow solves the problem. If all else fails, one can emulate the natural algorithm. The idea is to let raindrops fall on each grid point, and then follow the runoff as it drains toward lower elevations. The most thorough version of this algorithm pursues every downhill path. That is, if a point has three lower neighbors, then the algorithm follows droplets that roll along each of the three downhill links. The flow stops when the droplet reaches a pit and has nowhere more to go.

Tracing such paths for all points on the continent should identify the great divide. The divide is just the set of points from which droplets can reach both the Atlantic and the Pacific basins. (This is, after all, the definition of the divide.)

The rainfall algorithm works, at least for small test cases, but it is fabulously inefficient. An average point on the model landscape has two downhill neighbors, which means the number of paths to be explored doubles at every step. If a typical path is just 20 steps long, the algorithm will have to map a million paths for each point.

This exponential explosion of pathways should not be necessary. Real water droplets don’t explore all possible routes to the sea; for the most part, they stick to the path of steepest descent. An algorithm can do the same, which makes the computational burden much lighter. But there are other problems. The divide has to be defined somewhat differently—as a path threading between grid points rather than a connected series of points. And there is the lake-bottom problem: A path of steepest descent seldom descends continuously from the divide all the way to the ocean. It’s not all downhill from here.

Somewhere in North Dakota or Minnesota—near another divide that separates Hudson Bay from the Gulf of Mexico—I finally began to settle on an idea that might be called the global-warming algorithm. It works like this: Given North America in a terrarium, start raising the sea level, and keep the floods coming until the Atlantic and the Pacific just touch. At this moment you have identified one point—namely the lowest point—on the great divide. Now continue adding water, but as the sea level rises further don’t allow the two oceans to mix. (This would be a difficult trick in a physical model, and it’s none too easy even in a computer simulation.) Note the succession of points on the land where east meets west, and mark them down as elements of the divide. When the last such point is submerged, you have succeeded in dividing the continent.

Describing this process in terms of water filling a basin tends to conceal some of the nitty-gritty computational details. Real water is very good at flooding; it just knows how to do it and never makes a mistake. Simulated water, on the other hand, must meticulously plot its every move. To raise the level one foot, you have to check every point adjacent to the current waterline and decide which points will be newly submerged. Then you have to look at the neighbors of these selected points, and at their neighbors, and so on. There’s the potential for another exponential explosion here, although with realistic landscapes it doesn’t seem to happen.

When I finally got a chance to write a program for this process, I found that the algorithm is exquisitely sensitive to the order of operations. Consider the situation just as the Pacific is about to reach the lowest point on the divide. If the Atlantic has not been raised in synchrony, then the Pacific waters will pour over the saddle point and flood part of the eastern basin, shifting the divide to an incorrect position.

EMAIL TO A FRIEND :

Of Possible Interest

Computing Science: Computer Vision and Computer Hallucinations

Infographic: Orion's First Test Flight

Spotlight: Briefings