Suppose you need to walk through a wet parking lot. The lot is covered with puddles and you would like to keep your shoes as dry as possible. If you know the depth of the puddles at every point, how do you choose the path that minimizes the maximum depth of the puddles you cross? A hiker might want to solve a similar problem if they want to avoid fatigue by seeking low elevations. How do you traverse a mountainous area while remaining as low as possible?
To make the problem more formal, say the area of interest is and the elevation of the ground (or puddle depth) at each point is , with continuous. Choose areas that are acceptable start and finish points and call them and . If you want to walk from the north end of the square to the south, then you could choose and . The problem can be stated as the minimax
over continuous paths such that and .
Initially, you might suppose that this is a fundamentally continuous problem since there is a continuum of possible routes . However, we can make the problem discrete by considering sublevel sets of .
The -sublevel set of is the set of points where is below elevation , that is
The minimax problem is solved by finding a that lies in the lowest sublevel set connecting and . That lowest elevation is
Watch the animated figure below and notice the first time that the white sublevel set connects the top and bottom. A path between top and bottom must first appear when the boundaries pass through a saddle point of because saddle points are where connected components of sublevel sets join each other. This is a consequence of the “mountain pass theorem”: if is optimal and is maximized by , then is a stationary point of . That stationary point is a normally a saddle point (though it could be part of a flat-topped area).
Now we can write a discrete process for finding an optimal path:
- Locate all saddle points of .
- Order the saddle points by elevation so that .
- For each saddle point , determine whether its sublevel set has a connected component intersecting and .
- If the lowest such saddle point is , then is the minimum value for the minimax problem, and the optimal path is any contained in that connects and .
For something else to think about, let’s consider a connection to graph theory. If you watch the above animation a few times, you’ll notice that connected components of the white sublevel sets are created at local minima. They spread out and meet other components at saddle points. You might imagine a graph (or network) being created between the local minima: when two components touch, an edge is created between two minima (one in each component).
Is there a natural way to choose a representative from each component to connect? If a hole forms so that the component is no longer simply connected, should an edge be added to make a cycle? Also, a graph on the maxima could be created in the same way. Should the graph on the maxima be the dual of the graph on the minima?
Post any thoughts or questions in the comments below!