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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
2
|
|
||||||
|
|
5
|
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 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.  |
|||||||||||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
4
|
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. |
|||||||||||||||
|
