The mathematicians—5,130 of them, at last report—are in New Orleans this weekend. The occasion is the annual joint meeting of the American Mathematical Society and the Mathematical Association of America (with participation from several other organizations). When the same group met here six years ago, the influx of 5,000 mathematicians added 1 percent to the city’s population. Now it’s probably about 2 percent.
Over the next few days I’m going to write up some brief notes about a few of the talks I’ve heard here, and post some observations on the city itself. I’ve also set up a Flickr stream for photographs made on this trip, both in New Orleans and on the road to and from. See the pictures here.
For now, just one quick note on city geography.
The founders of New Orleans laid out a rectilinear grid of streets aligned parallel and perpendicular to the Mississippi River; in the map above the original grid is the section marked Vieux Carré. As the city expanded both upriver and downriver, the planners had a problem: The river is anything but straight. The solution they chose was a patchwork of locally rectilinear lattices with discontinuities between them. I am particularly conscious of the discontinuities because the route from my hotel to the meeting site crosses one of them, between the Vieux Carré and the Faubourg Marigny. (In the map above, my hotel is at the position of the green marker, and most of the meeting events are at the red marker; the route shown is the one suggested by Google Maps.) When I first looked at the map, I thought the street pattern offered me a stroke of good fortune. If the entire city had been ruled according to the grid in the neighborhood of my hotel, I would have had a much longer walk; the 45-degree bend at Kerlerec Street allows me to take a diagonal shortcut for much of the trip. But then I reflected that if the Vieux Carré grid had been adopted everywhere, my walk would have been even shorter.
In this particular case, the route proposed by Google looks like an optimal one; that is, if we ignore certain oddities induced by one-way streets, there is no other path that would be significantly shorter. But, more generally, how does one find the best route through a grid with discontinuities? Within any one section of the grid, distance is measured by the Manhattan metric (s = x + y), and all reasonable paths are equivalent. (A path is reasonable if it stays within the smallest rectangle enclosing the origin and destination and if it never moves away from the destination.) Thus the problem comes down to choosing the point along the line of discontinuity where you cross over from one grid to the other. What is the rule for choosing the best crossover point? Is it unique or are there multiple equivalent points?
Update 2007-01-09. This is in response to Stephan Mertens’ suggestion in the comment below. His proposal to choose the crossing point nearest to where a straight line intersects the boundary is doubtless excellent practical advice, useful for navigating in the real world. But we’re talking mathematics here, and usefulness in the real world has nothing to do with it. Does Mertens’ method always produce the mathematically optimal path?
Consider the continuous case—the limit you reach as the lattice spacing goes to zero. What you have then are two anisotropic media where speed varies with direction; in the worst case you are slowed down by a factor of √2. Does the straight-line heuristic work in this case? I think not. The situation is similar to (but a little more complicated than) the description of a light ray traversing a boundary between two media that differ in index of refraction. Light bends at such a boundary, following the path that minimizes the total travel time.
Going back to the discrete-lattice case, it’s not quite clear (to me, at least) how to apply the continuum solution, because the problem itself is not very clearly stated. If the two lattices have the same spacing but different orientations, then they are incommensurable, and adjustments of some kind have to be made all along the boundary. In the real New Orleans street grid, this is done in an ad hoc way; note, for example, that Bourbon Street disappears when you leave the Vieux Carré. Any precise statement of the problem would have to say just how the grids are joined, and that gets messy. Nevertheless, I offer the example below for consideration.
Here we want to navigate between the red points. The straight-line heuristic appears to recommend crossing the boundary at the blue point, but there are shorter paths via the green point.
Update 2007-01-12. After further forthing and backing, Stephan Mertens and I have agreed not to disagree about this issue. In order to avoid the messy problem of drawing streets to connect unaligned lattices, Mertens makes the civilized suggestion that we build a park in the interstices, like so:
Within the park, a walker is freed from the constraints of the lattice and can follow any Euclidean path. In the case shown above, either the green or the yellow path (or many others) would be allowed. Mertens writes:
For this simple model one can write down the distance between a point in the left and a point in the right grid, as a function of the transition points where the walker enters or leaves the transition region. It is most convenient to use different coordinate system in the grids: Both have (0,0) at the point where the grids touch and increase y moving upward and x moving away from the crack. Note that the y coordinate of the transition point can vary continously since the walker may decide to leave the grid everywhere on the street that runs along the crack.
The resulting function can be plotted with Mathematica; apparently the minimum is unique, and a strategy that seems to be not too far off (this time I am cautious with my claims!) is to pass the through the park using the two gateways that have the y coordinates of source and target. In other words: Run all the way straight in each grid to reach the transition region.
There are cases where the run-straight-to-the-park strategy differs substantially from the procedure of drawing a straight line from origin to destination. The example below (where the yellow path is shorter than the red one) offers a template for generating street grids in which the penalty for choosing the straight-line path becomes arbitrarily large.
