MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 Removed now irrelevant example.

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:The view from $s$ only shows edges surrounding the weight-10 region, and from that point ofview, your algorithm would select to cross the weight-9 region (if I understand it correctly). However, that weight-11region is "hiding"

[My first counterexample was based on a low-weight region, which would be much more economical to traverse.It does not seem to me one can determine "the sequence misinterpretation ofpolygons through which the shortest path will pass" only by looking at the edge weightsto either side region-separating edges.My sense is that determining the sequence of polygons the shortest path crosses isabout as difficult ; now removed as finding irrelevant (but this explains the true shortest pathcomments below). Counterexample to a correct interpretation follows.]

show/hide this revision's text 2 New counterexample after clarification of the edge weights.

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

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 lengthof 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.Your algorithm would select the purple path, because its cost is $0+\frac{3}{2}+0$, whereas the red pathhas 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 edgesin 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 theonly 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 convexregion overestimates the cost of traversing through the interior of that region,and this overestimate could lead to the algorithm choosing a nonoptimal route.
show/hide this revision's text 1

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
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.