[math-fun] Jaywalker geometry (was Re: Disks in Euclidean approximation metrics ...)
Brad Klee <bradklee@gmail.com> wrote:
I really love lattice walk problems, think that they are entirely practical, and with many branch points into other areas of mathematics and physics.
A variant of taxicab geometry I came up with is jaywalker geometry. Envision the roads having, not zero width, but infinitesimal width. Distance is defined, not as how far a taxicab drives, but as how far a jaywalker walks. If a right turn is to be followed by a left turn or vice versa, to minimize his walking distance he crosses the street diagonally, over the whole length of it that he traverses, much to the annoyance of the taxicabs. In taxicab geometry there are in general lots of shortest paths between any two grid points, but in jaywalker geometry, of all those paths, the paths with the most turns are shortest. I think those paths are the ones that approximate Euclidean paths most closely. For instance instead of walking ten blocks north then ten blocks east, the jaywalker would alternate between walking one block north and one block east. Has anyone else played with this?
=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!
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
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
Thanks for the clarifications! Silly me, my mistake was taking "infinitesimal" too literally. OK, so one way to visualize this is finding short paths in the plane that must avoid "obstructions". Specifically here the obstructions are an infinite grid of (open?) square blocks of width 1-2h centered at the half-integers, with sides parallel to the axis. It's interesting to see how the bundles of minimal paths changes as h varies from 1/2 (taxicab) to 0 (Euclidean). We can also play with the design of the city. For example we could have a hexagonal tiling, or change the blocks to be an "orchard" of circular obstructions, or little linear cuts you can't cross, or even fractals. And instead of an endless grid you could have just a single forbidden disk, say the unit circle. Then almost all minimal paths are Euclidean, except a subset where the endpoints are "shadowed" from each other by the obstruction. Maybe roboticists that do path planning and obstacle avoidance might have some ideas?
There's some ambiguity around the endpoints of these paths. It looks like you've defined them as being in the centers of the street intersections at the initial and final endpoints (which is pretty extreme jaywalking). I had thought of each endpoint as being at one of the 4 corners of an intersection, which affects the path length, as well as the optimal path choices. In this case, the specific start and finish corners would need to be specified in order for the problem to be well-defined. In either case, you can think of these distances as the result of running a string along the segments of the path, then pulling it taught (assuming each block has buildings at its corners to stop the string). Tom Gareth McCaughan writes:
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
participants (5)
-
Allan Wechsler -
Gareth McCaughan -
Keith F. Lynch -
Marc LeBrun -
Tom Karzes