MY AMERICAN SCIENTIST
SEARCH

COMPUTING SCIENCE

# Think Globally, Classify Locally

How should the terrain inside the box be represented mathematically? One elegant idea is to make the earth’s surface the graph of a continuous function h(x,y), which defines a height h for every combination of x and y coordinates. (I assume the spherical surface is projected onto a plane. Also, it’s necessary to smooth out cliffs and overhangs, so that every x,y pair yields a unique h.) The main advantage of this scheme is that you can find maxima and minima of the height function by taking the derivative of h and looking for its zeroes. The disadvantage is that an equation for all of North America is likely to be quite unwieldy.

A more practical alternative is a discrete model, defining the elevation of the surface only at a finite number of points arranged in a grid. To keep things simple, let the grid be rectangular, formed by the intersections of evenly spaced north-south and east-west lines. Also, connect each grid point only to its four nearest neighbors, so that water on the model landscape flows only in the four cardinal directions. With this model of the terrain, the task of a continental-divide algorithm can be stated more concretely. For each grid point, the algorithm must answer the question: Does this point lie on the divide? Does it shed water into two basins that do not communicate with each other?

As we motored on into Montana, I tried to come up with a quick-and-easy algorithm to answer these questions. My first thought was to make the most of local information about the immediate neighborhood surrounding each point. I reasoned that the divide ought to run mainly along ridges, and ridges can be recognized by a distinctive pattern of higher and lower neighbors.

But analyzing neighborhoods proved messy. Each of a point’s four neighbors can be above, below or level with the central point, and so there are 34=81 possible configurations. That was too many cases to keep in mind while cruising down the Interstate, so I decided to simplify by pretending that no two adjacent grid points are ever at exactly the same height. (This ruse is not as unrealistic as it might seem; if you could measure elevations with infinite precision, the probability of finding two identical values would be zero.)

When all neighbors must be either higher or lower, there are 16 local configurations, and they can be further consolidated into just six classes. A peak is a point higher than all four of its neighbors, and a pit is lower than all of its neighbors. A point with exactly three lower neighbors lies on a ridgeline. The opposite case of three higher neighbors describes points along a valley bottom—a line known to topographers and crossword solvers as a thalweg. Finally, the points with equal numbers of higher and lower neighbors fall into two subclasses. If you stand on the central point and turn through 360 degrees to survey the neighbors, you might see them in a sequence such as above-above-below-below; a point of this kind lies on a slope. If the neighbors alternate, as in the sequence above-below-above-below, then the point is a saddle or pass. A saddle is special: It is the only kind of point that lies both on a ridgeline and on a thalweg.

EMAIL TO A FRIEND :

Of Possible Interest

Computing Science: Computer Vision and Computer Hallucinations

Infographic: Orion's First Test Flight

Spotlight: Briefings