3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ An earlier version of this problem was posted, closed, and deleted as mathoverflow.net/questions/95220/…. This version looks a little better. $\endgroup$ May 1, 2012 at 5:34
  • $\begingroup$ I don't understand the downvotes. It strikes me as a clear, specific question. I retagged it and corrected the English. $\endgroup$ May 1, 2012 at 11:33

2 Answers 2

6
$\begingroup$

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.


     Many Shortest Paths

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.
      Many Shortest Paths


$\endgroup$
9
  • $\begingroup$ Nice construction. This can be changed so that the triangles don't touch, but I don't know whether OP means such a restriction anyway. $\endgroup$ May 1, 2012 at 13:26
  • $\begingroup$ @Zsbán: Yes, agreed! $\endgroup$ May 1, 2012 at 19:14
  • $\begingroup$ You should make it clear that the long blue triangles have length (base) dependent on the number of components. If one is satisfied with dividing squares into two, I think that a modified Manhattan grid could provide another exponential example, if sufficient care were taken at intersections, or if each square was augmented so as to encourage the traveler to go down the middle of each street. Gerhard "Ask Me About System Design" Paseman, 2012.05.01 $\endgroup$ May 1, 2012 at 20:50
  • $\begingroup$ @Gerhard: You are right about the length of the triangles. That's what the arrows were intended to suggest. I also agree your grid example could work, with "sufficient care." :-) $\endgroup$ May 1, 2012 at 20:55
  • $\begingroup$ Joseph, I think you can skip those dents in the red diamonds and get back to $2^{n/3}$ paths if you draw a tower with an odd number of yellow triangles with every other one offset a little bit, say to the left of center, and use the blue triangles to pinch the path and push it over, resulting in a picture consisting of a bunch of red diamonds connected by short segments (of length $d$) that zigzag back and forth. (Come to think of it, you could do it with an even number of yellow triangles, just by tilting things appropriately.) Or am I missing something? $\endgroup$ May 1, 2012 at 21:50
5
$\begingroup$

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]
     Shortest Paths

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.

$\endgroup$
6
  • $\begingroup$ For more components but of bounded size, take m x n laterally shifted copies of the rectangle with vertices (1,0), (0,1), and (epsilon, epsilon) for appropriate epsilon, say epsilon = 1/100, and place so the centroids are in an mxn square grid; There will be superpolynomially many paths of length m+n from the origin to (m,n). This uses only bounded isosceles triangles, although it uses many more of them. Gerhard "Ask Me About System Design" Paseman, 2012.05.01 $\endgroup$ May 1, 2012 at 22:54
  • $\begingroup$ oops, I meant shifted copies of the triangle. Gerhard "Really, I Was Thinking Triangle" Paseman, 2012.05.01 $\endgroup$ May 1, 2012 at 22:55
  • $\begingroup$ Oops again. It looks like have n+m fences with that arrangement, and only two paths. Perhaps a grid arrangement will work, but I will stop here. Gerhard "Cares To Stop Insufficient Care" Paseman, 2012.05.01 $\endgroup$ May 1, 2012 at 23:30
  • $\begingroup$ @Barry: I added a figure, taking some liberties: (a) I used segments instead of triangles; (b) I did not follow your coordinates for the yellow splitters, but I hope captured your (nice!) idea. $\endgroup$ May 2, 2012 at 0:58
  • $\begingroup$ @Barry: Nice new construction! (I'm traveling and cannot play a draftsman role.) $\endgroup$ May 2, 2012 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.