The red and orange lines show two possible routes I could take. The orange path more closely approximates the optimal hypotenuse to the red path, but it's not really any shorter, since I can still only walk due south and due east, right?
No, actually. If each intersection were a point, and each street a one dimensional line segment, then it would be no different. But in fact, each street is a narrow rectangle, and being sleepy residential streets, I can walk their diagonals, thereby saving precious distance. In other words, my optimal route actually looks something like this:
Scoff though you might, even in this small example the optimal route is about 80 meters shorter than the naive route. Try telling this guy that's not a significant savings.
In this part of Corvallis, each block is 60m in the east-west direction and 80m in the north-south direction, estimated from Google Maps. A street, from the outer edge of the sidewalk to outer edge of the opposite sidewalk is approximately 15m. So the distance of the naive route is, 4 north-south blocks + 4 east-west blocks + 6 intersections interspersed throughout.
Naive route = 4*80m + 4*60m + 6*15m = 650m
For the optimal route we must calculate the diagonal of one block of an east-west street, and the diagonal of one block of a north-south street. These are just the hypotenuses of 15x60 and 15x80 right triangles, respectively.
sqrt(15^2 + 60^2) = approx. 61.8
sqrt(15^2 + 80^2) = approx. 81.4
Optimal route = 80m + 3*61.8m + 3*81.4m + 60m = approx. 570m
If we ignore the first and last blocks and only count the portions of each route that differ, the difference is 510m to 430m, more than a 15% distance savings over that portion of the route. Or put another way, a perfect diagonal would be 363m (a 29% savings), so we are actually closer to the hypothetical perfect route than the naive route.
Of course, with longer blocks or narrower streets, the relative improvement of this technique over a naive route will be smaller, while with shorter blocks or wider streets it will be greater.
An additional advantage to this technique is that by zigzagging through side streets you increase your chances of finding a corner parking lot, empty lot, or city park allowing you to cut even more meterage off your trek through diagonalization.
I hope this has been as enlightening for you as it was time-wasting for me. May you all get where you need to go more quickly and less sweaty.
4 comments: