Return to Answer

[My first counterexample was based on a misinterpretation of the edge weights; now removed as irrelevant (but this explains the comments below). Counterexample to a correct interpretation follows.]

---

Added. (30Jul11). Sorry for misinterpreting. I now see that the weight of each edge in your graph is the Euclidean length of the edge times the lower weight of the region to either side. Here is an example where I believe the algorithm fails, where I use $w$ for weight and $l$ for length.
           ![shortest 2][2]
Your algorithm would select the purple path, because its cost is $0+\frac{3}{2}+0$, whereas the red path has cost about $0+\frac{\pi}{2}+0 > \frac{3}{2}$, and so is rejected by the algorithm. (Of course I could make the red cost approach $\frac{\pi}{2}$ by increasing the number of edges in the regular polygon; the zero weights could be $\epsilon$-weights if you want them all to be positive). I am assuming surrounding regions that lead to the weights shown being the only relevant ones. So the algorithm thinks passing through the mauve rectangle is best. But the green path (not visible to your algorithm because it does not follow edges of regions) has cost $0+1+0$. The problem is that following the edges of a convex region overestimates the cost of traversing through the interior of that region, and this overestimate could lead to the algorithm choosing a nonoptimal route.

[My first counterexample was based on a misinterpretation of the edge weights; now removed as irrelevant (but this explains the comments below). Counterexample to a correct interpretation follows.]

---

Added. (30Jul11). Sorry for misinterpreting. I now see that the weight of each edge in your graph is the Euclidean length of the edge times the lower weight of the region to either side. Here is an example where I believe the algorithm fails, where I use $w$ for weight and $l$ for length.
           ![shortest 2][2]
Your algorithm would select the purple path, because its cost is $0+\frac{3}{2}+0$, whereas the red path has cost about $0+\frac{\pi}{2}+0 > \frac{3}{2}$, and so is rejected by the algorithm. (Of course I could make the red cost approach $\frac{\pi}{2}$ by increasing the number of edges in the regular polygon; the zero weights could be $\epsilon$-weights if you want them all to be positive). I am assuming surrounding regions that lead to the weights shown being the only relevant ones. So the algorithm thinks passing through the mauve rectangle is best. But the green path (not visible to your algorithm because it does not follow edges of regions) has cost $0+1+0$. The problem is that following the edges of a convex region overestimates the cost of traversing through the interior of that region, and this overestimate could lead to the algorithm choosing a nonoptimal route.

Edit (30Jul11). Indeed I misinterpreted the algorithm. I'll leave this here for the record, but see below the horizontal rule.

Likely I have misunderstood your idea, but under one interpretation, I do not think it can work, for the following reason. Consider an example like this:
           shortest http://cs.smith.edu/%7Eorourke/MathOverflow/ShortestWeighted.jpg
The view from $s$ only shows edges surrounding the weight-10 region, and from that point of view, your algorithm would select to cross the weight-9 region (if I understand it correctly). However, that weight-11 region is "hiding" a low-weight region, which would be much more economical to traverse. It does not seem to me one can determine "the sequence of polygons through which the shortest path will pass" only by looking at the weights to either side region-separating edges. My sense is that determining the sequence of polygons the shortest path crosses is about as difficult as finding the true shortest path.

---

Added. (30Jul11). Sorry for misinterpreting. I now see that the weight of each edge in your graph is the Euclidean length of the edge times the lower weight of the region to either side. Here is an example where I believe the algorithm fails, where I use $w$ for weight and $l$ for length.
           ![shortest 2][2]
Your algorithm would select the purple path, because its cost is $0+\frac{3}{2}+0$, whereas the red path has cost about $0+\frac{\pi}{2}+0 > \frac{3}{2}$, and so is rejected by the algorithm. (Of course I could make the red cost approach $\frac{\pi}{2}$ by increasing the number of edges in the regular polygon; the zero weights could be $\epsilon$-weights if you want them all to be positive). I am assuming surrounding regions that lead to the weights shown being the only relevant ones. So the algorithm thinks passing through the mauve rectangle is best. But the green path (not visible to your algorithm because it does not follow edges of regions) has cost $0+1+0$. The problem is that following the edges of a convex region overestimates the cost of traversing through the interior of that region, and this overestimate could lead to the algorithm choosing a nonoptimal route.

[My first counterexample was based on a misinterpretation of the edge weights; now removed as irrelevant (but this explains the comments below). Counterexample to a correct interpretation follows.]

---

Added. (30Jul11). Sorry for misinterpreting. I now see that the weight of each edge in your graph is the Euclidean length of the edge times the lower weight of the region to either side. Here is an example where I believe the algorithm fails, where I use $w$ for weight and $l$ for length.
           ![shortest 2][2]
Your algorithm would select the purple path, because its cost is $0+\frac{3}{2}+0$, whereas the red path has cost about $0+\frac{\pi}{2}+0 > \frac{3}{2}$, and so is rejected by the algorithm. (Of course I could make the red cost approach $\frac{\pi}{2}$ by increasing the number of edges in the regular polygon; the zero weights could be $\epsilon$-weights if you want them all to be positive). I am assuming surrounding regions that lead to the weights shown being the only relevant ones. So the algorithm thinks passing through the mauve rectangle is best. But the green path (not visible to your algorithm because it does not follow edges of regions) has cost $0+1+0$. The problem is that following the edges of a convex region overestimates the cost of traversing through the interior of that region, and this overestimate could lead to the algorithm choosing a nonoptimal route.

Likely I have misunderstood your idea, but under one interpretation, I do not think it can work, for the following reason. Consider an example like this:
           shortest http://cs.smith.edu/%7Eorourke/MathOverflow/ShortestWeighted.jpg
The view from $s$ only shows edges surrounding the weight-10 region, and from that point of view, your algorithm would select to cross the weight-9 region (if I understand it correctly). However, that weight-11 region is "hiding" a low-weight region, which would be much more economical to traverse. It does not seem to me one can determine "the sequence of polygons through which the shortest path will pass" only by looking at the weights to either side region-separating edges. My sense is that determining the sequence of polygons the shortest path crosses is about as difficult as finding the true shortest path.

Edit (30Jul11). Indeed I misinterpreted the algorithm. I'll leave this here for the record, but see below the horizontal rule.

Likely I have misunderstood your idea, but under one interpretation, I do not think it can work, for the following reason. Consider an example like this:
           shortest http://cs.smith.edu/%7Eorourke/MathOverflow/ShortestWeighted.jpg
The view from $s$ only shows edges surrounding the weight-10 region, and from that point of view, your algorithm would select to cross the weight-9 region (if I understand it correctly). However, that weight-11 region is "hiding" a low-weight region, which would be much more economical to traverse. It does not seem to me one can determine "the sequence of polygons through which the shortest path will pass" only by looking at the weights to either side region-separating edges. My sense is that determining the sequence of polygons the shortest path crosses is about as difficult as finding the true shortest path.

---

Added. (30Jul11). Sorry for misinterpreting. I now see that the weight of each edge in your graph is the Euclidean length of the edge times the lower weight of the region to either side. Here is an example where I believe the algorithm fails, where I use $w$ for weight and $l$ for length.
           ![shortest 2][2]
Your algorithm would select the purple path, because its cost is $0+\frac{3}{2}+0$, whereas the red path has cost about $0+\frac{\pi}{2}+0 > \frac{3}{2}$, and so is rejected by the algorithm. (Of course I could make the red cost approach $\frac{\pi}{2}$ by increasing the number of edges in the regular polygon; the zero weights could be $\epsilon$-weights if you want them all to be positive). I am assuming surrounding regions that lead to the weights shown being the only relevant ones. So the algorithm thinks passing through the mauve rectangle is best. But the green path (not visible to your algorithm because it does not follow edges of regions) has cost $0+1+0$. The problem is that following the edges of a convex region overestimates the cost of traversing through the interior of that region, and this overestimate could lead to the algorithm choosing a nonoptimal route.