Timeline for maximum number of shortest path among a set of n triangle obstacles
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 8, 2017 at 10:42 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Image links broken; now fixed.
|
| May 2, 2012 at 12:48 | comment | added | Joseph O'Rourke | @JeffE: :-) $\mbox{}$ | |
| May 2, 2012 at 12:44 | comment | added | JeffE | @Joe: Gerhard's grid idea works immediately if the obstacles are open squares. On the other hand, in the plane minus closed triangles, then technically there are no shortest paths except straight line segments! (How's that for "sufficient care"?) | |
| May 1, 2012 at 23:43 | comment | added | Joseph O'Rourke | @Barry & Gerhard: Yes, I see other options, each requiring some care. But rather than worry about whether the constant in the exponent is $\frac{1}{5}$ or $\frac{1}{3}$, it might be more interesting to try to achieve an exponential number of paths within bounded coordinates for the triangle corners, which my construction does not achieve. | |
| May 1, 2012 at 22:31 | comment | added | Gerhard Paseman | One needs sufficient care to make sure no other shortest paths sneak in, Barry; otherwise I agree that the exponent could be raised to n/3 where n is the number of obstacles, if obstacle size is unbounded. Perhaps you can provide the "sufficient care" needed to tweak Joseph's construct or come up with one based on my grid suggestion? Gerhard "Ask Me About System Design" Paseman, 2012.05.01 | |
| May 1, 2012 at 21:50 | comment | added | Barry Cipra | 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? | |
| May 1, 2012 at 20:55 | comment | added | Joseph O'Rourke | @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." :-) | |
| May 1, 2012 at 20:50 | comment | added | Gerhard Paseman | 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 | |
| May 1, 2012 at 19:14 | comment | added | Joseph O'Rourke | @Zsbán: Yes, agreed! | |
| May 1, 2012 at 19:12 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Disjoint triangles.; added 7 characters in body
|
| May 1, 2012 at 13:26 | comment | added | Zsbán Ambrus | 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. | |
| May 1, 2012 at 12:23 | history | answered | Joseph O'Rourke | CC BY-SA 3.0 |