Math on the Mississippi

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.

New Orleans street grid

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.

incommensurable grids

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.

This entry was posted in mathematics.

6 Responses to Math on the Mississippi

  1. Draw a straight line on the map between your hotel and the destination in the tilted grid. Take the transition point that is closest to the point where this line intersects the discontinuity. This should give the shortest distance, and apparently Google knows that.

    Stephan

  2. Let us assume equal lattice spacings in both parts of the grid (like in your counter example).
    Can you think of an example where the straight line heuristics is off by *more* than one block?

  3. Barry Cipra says:

    “If the two lattices have the same spacing but different orientations, then they are incommensurable…” This isn’t quite correct. Integer solutions of the Pythagorean formula a^2 + b^2 = c^2 allow for commensurable orientations — e.g., a slope of 3/4 permits a 5-way intersection at every fifth corner for the tilted grid. (One would presumably extend each untilted street till it meets the boundary of the tilted grid. Otherwise there could be some fairly long detours.)

  4. brian says:

    “Incommensurable” was sloppy wording on my part. I simply meant that you cannot make *all* the intersections line up neatly (unless the angle is a multiple of 90 degrees).

    Incidentally, although the blocks in New Orleans are roughly square, other cities favor elongated rectangles; Manhattan, for example, has short blocks along the avenues and longer blocks along the cross streets. If you build a city by knitting together adjacent patches of grid rotated by 45 degrees, there’s a very nice solution with blocks whose aspect ratio is 1:√2.

  5. Jasper Crowe says:

    I think the following proves Merten’s algorithm is the best possible:
    Let the point in the (x’,y’) lattice be at (X’,Y’) and let the point in the (x,y) lattice be (X,Y). Any path from (X’,Y’) to (X,Y) has three segments:
    1) we travel from (X’,Y’) through the (x’,y’) lattice until we reach x’=0. Call this point (0,b’).
    2) we walk through the park to the line x=0. Call this point (0,b).
    3) we travel through the (x,y) lattice from (0,b) to (X,Y).

    In 1), note that any direct path you take from (X’,Y’) to (0,b’) (by this I mean any path such that the Manhattan distance to (0,b’) is strictly decreasing) has the same distance as just walking from (X’,Y’) to (0,Y’) and then walking from (0,Y’) to (0,b’). And similarly for 2). This reduces the problem to finding b, b’ so that the sum of the following distances is minimized:
    1) from (0,Y’) to (0,b’) (along the y’ axis)
    2) from (0,b’) to (0,b) (through the park)
    3) from (0,b) to (0,Y) (along the y axis)

    The distance we are trying to minimize is (b’-Y’)+(b-Y)+|V| where V is the vector in 2). We’d like to show that this is less than |U| where U is the vector from (0,Y’) to (0,Y) (i.e. where b’=Y’ and b=Y). Let /y’/ be the unit vector in the +y’ direction and /y/ be the unit vector in the +y direction. Then we have the following vector sum:

    (b’-Y’)/y’/+(b-Y)/y/+V=U
    It follows from the triangle inequality that

    |(b’-Y’)/y’/|+|(b-Y)/y/|+|V|

  6. Jasper Crowne says:

    I just realized that my comment was cut off (most likely due to use of the less than sign), and that I misspelled my name…

    It follows from the triangle inequality that

    |(b’-Y’)/y’/|+|(b-Y)/y/|+|V| is less than or equal to |U|; since /y/ and /y’/ are arbitrary in the general case, we have equality only when b=Y, b’=Y’, and hence V=U. QED