maximum number of shortest path among a set of n triangle obstacles

2012-05-01T04:47:32Z

Assume that we have a two distinct points. The number of shortest path between these two points is one. When we add a triangle obstacle to the plane and this triangle intersects the line connecting two above points. The possible maximum number of shortest path in this case is two (depending on how we add the triangle). So how does the number of shortest paths change if we continue adding triangles to the plane? What is the maximum possible number of shortest paths between two points among a set of $n$ triangle obstacles?

Answer by Joseph O'Rourke for maximum number of shortest path among a set of n triangle obstacles

2012-05-01T12:23:19Z

The construction below achieves $2^{c n}$ for constant $c$ (e.g., $c=\frac{1}{3}$). But it is flawed in that I have two triangles sharing a vertex and paths passing through that vertex. It is natural to insist that the triangles be disjoint. I think the same basic construction can accomplish a $2^{c n}$ bound by (a) separating the touching triangles, while (b) arranging a detour that makes a turn at the center of the X exactly the same length as shooting straight through on a diagonal. But I have not carried through the construction in detail.

Update. Here is an exponential construction using disjoint triangles, where the marked lengths satisfy $a=b+c$. Length $d$ is shared by all paths. Here there are $2^2=4$ paths, and $2^{1+(n-1)/5}$ for $n$ triangles.

Answer by Barry Cipra for maximum number of shortest path among a set of n triangle obstacles

2012-05-01T22:39:08Z

Here's a variant on Joseph O'Rourke's construction that produces $2^{n/2}$ paths. I don't have Joseph's knack for drawing pictures, so I'll describe it in words with an example. (I'd be delighted if he would replace my words with a picture.)

Let's connect the origin $(0,0)$ to $(0,10)$. Start by laying down a series of extremely long, extremely skinny, "blue" triangles that come in horizontally from the left to $(1,1)$, from the right to $(-1,3)$, from the left to $(1,5)$, from the right to $(-1,7)$, and from the left to $(1,9)$. At this point there's just one shortest path, which zigzags from $(0,0)$ to $(1,1)$ to $(-1,3)$ to $(1,5)$ to $(-1,7)$ to $(1,9)$ to $(0,10)$. Now on each of these segments put one of O'Rourke's little yellow "splitters" -- in particular, say, at $(0,2)$, $(0,4)$, $(0,6)$, and $(0,8)$.

In general, if you use $k$ long blue triangle to create a zigzag path and put a yellow splitter on each of the $k+1$ segments of the zigzag, you get $2^{[(n+1)/2]}$ shortest paths, where $n=2k+1$.

[Added by O'Rourke]

Added later on 5/1/12: Let me paint another word picture of a construction that's better in a couple of respects. For one, it answer's Gerhard Paseman's concern over alternative shorter paths sneaking in. It also makes clear that the construction can be continued indefinitely, with the number of shortest paths doubling with each pair of additional triangles (one "blue" and one "yellow").

Suppose we have an infinite supply of long, thin blue triangles ready to come in horizontally, all from the right, at heights $1, 1/2, 1/3, 1/4$, etc. Let's start with the shortest path from $(0,2)$ to $(0,0)$ -- i.e., a vertical line segment -- and imagine it as a rubber band. Now bring in the first $n$ blue triangles, at heights $1$ to $1/n$, and poke the rubber band over so that, starting at $(0,2)$, it now follows line segments of slope $1, 2, 3, \ldots, n$ and negative something to $(0,0)$. (It shouldn't be hard to work out exactly where the poke points are and what the final negative-something slope is, but the odds of my doing so correctly are vanishingly small, and it's really not necessary for the argument, which is mainly qualitative.)

If you draw the picture (and I'm hoping Joseph will do so again!), it's easy to see that the path to this point has length less than 5 (it's shorter than the path from $(0,2)$ to $(-2,0)$ to $(0,0)$), so if we assume the blue triangles are of length, say 10, we don't have to worry about anything sneaking around them. It's also easy to see that it's possible to put a tiny yellow "splitter" at the midpoint of each segment of positive slope that can't "see" anything of interest along the rubber band beyond the blue triangles that define its segment. This gives $2^n$ shortest paths using $2n$ triangles, with the option of letting $n$ go to infinity without having to change anything that's already in place.

Note: It's worth adding that this still doesn't solve the original problem of determining the maximum possible number of shortest paths when you put triangular obstacles between two points (or if it does, it does so without any proof). It just gives a lower bound on what can be done.

maximum number of shortest path among a set of n triangle obstacles - MathOverflow

maximum number of shortest path among a set of n triangle obstacles

Answer by Joseph O'Rourke for maximum number of shortest path among a set of n triangle obstacles

Answer by Barry Cipra for maximum number of shortest path among a set of n triangle obstacles