MY AMERICAN SCIENTIST
SEARCH

COMPUTING SCIENCE

# Divide and Conquer

Over the next 200 miles, as we followed the eastbound Yellowstone River, I had several more bright ideas that proved faulty. For example, I thought I saw a way to extend the ant-farm algorithm to the 3D world. The first step would be to survey elevations along the south wall of the terrarium, and find the maximum. Then set out from this peak, moving to the highest neighboring point, then to the highest neighbor of that point, and so on. Stop when you come to another wall or when the path loops back on itself. I briefly believed that this procedure would trace out the divide. I had forgotten that the high point on the southern boundary is not necessarily on the divide, and so you might go wrong from the first step.

An attempt to patch up this idea led to another strategy, which I still find appealing even though it seems to be a dead end. Suppose you know the two points where a divide touches the perimeter of a square region, but the path through the interior of the square is entirely hidden. If you could cut the square into four smaller tiles, and determine where the divide crosses each of their sides (if at all), then you would begin to have a rough vision of its route. Quartering each of these squares yields 16 more, and then 64. Soon, it would be enough merely to know which sides of a square are crossed by the path, without trying to measure the exact position of the intercept. This is a classic divide-and-conquer algorithm, with a hint of deep recursive magic. Unfortunately, the magic is illusion. The algorithm’s initial supposition—that we know where the divide enters and exits each square—is unfounded.

Yet another idea also exploits the distinctive topology of the divide—the fact that it is either a closed curve or a curve with endpoints anchored to the boundary. Here’s the plan. Working from local neighborhood information, identify all the peaks and ridgelines, and paint them red. The labeled ridges will form a dense network, which probably traverses most or all of the divide, but it includes many other paths as well. To be able to see the divide clearly, you need to prune away the underbrush. Topology suggests a promising way to do it. The premise is that all the ridges except the divide must have at least one free end—a dangling terminal point like the end of a tree limb. You can find these free ends by scanning the array for red points that have only one red neighbor. Removing the end point creates a new vulnerable stump. If you repeat the scan until no more single-neighbor sites can be found, only the divide will remain labeled—or so I thought.

In some instances this procedure actually works, but it has serious weaknesses. In the first place, as noted above, the divide does not have to lie entirely on peaks and ridges, and so the first stage of the algorithm may fail to label some points it should. The second stage can also introduce errors. Suppose two closed loops of the divide are connected by a ridge that is not properly part of the divide system (water on both sides flows to the same basin). Because this extraneous section of ridge has no free end, it cannot be removed by the pruning procedure.

EMAIL TO A FRIEND :

Of Possible Interest

Computing Science: Computer Vision and Computer Hallucinations

Infographic: Orion's First Test Flight

Spotlight: Briefings