It's possible that a diagnostic case would be to find the shortest path from (0,0) to, say, (18,2). If Keith Lynch's intuition is right, we would expect something like (0,0), (6-h, h), (6+h, 1-h), (12-h, 1+h), (12+h, 2-h), (18,2). But if Gareth McCaughan's concern is justified, then something like (0,0), (1-h, h), (1+h, 1-h), (2-h, 1+h), (2+h, 2-h), (18, 2) will be better, because it takes more consecutive single east and north steps. I don't have a strong judgement one way or the other, and at the moment I'm too lazy to do the algebra. Hope somebody settles this. On Sun, Oct 18, 2020 at 7:11 PM Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 18/10/2020 21:39, Marc LeBrun wrote:
=Keith F. Lynch Envision the roads having, not zero width, but infinitesimal width.
It sounds fascinating, but I'm really having trouble picturing this. Are the grid points at the intersections of these narrow-most roads? Are the jays walking "diagonally" along them or across them or what? You imply the shortest path from 0,0 to 2,2 goes thru 1,1. But why? Given some arbitrary path from A to B, how do we compute its length? Can you help by providing some worked examples or the like? Thanks!
A shortest path from (0,0) to (2,2) goes (0,0) (1-h,h) (1+h,1-h) (2-h,1+h) (2,2) where h is half the width of the roads. The total distance is some unpleasant thing involving square roots of quadratics in h, but e.g. with h=0.001 it's about 3.994 whereas the path that goes (0,0) - (2-h,h) - (2,2) has length about 3.998.
Taking a route that stays nearer to a straight line lets you cut the corners slightly more effectively.
I'm not sure it's actually correct to say that this rewards staying closer to the straight line, though, because I think really all it's doing is rewarding _alternation_ between going north and going east, and in general there will be lots of equally-good paths, some of which will stay much closer than others to the straight-line path.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun