Manhattan distance

Manhattan path  

For example, the diagram shows the path from to . A Manhattan resident has to make 4 steps to get from one stone to another. The underlying geometry is called taxicab geometry. (For more information read the book Taxicab Geometry by Eugene F. Krause, published by Dover in 1987. ISBN 0-486-25202-7. Amazon)

A Circle with Radius 9 in Taxicab Geometry  

A "circle" is defined as the set of all points that have the same distance from a given point.

Fhayashi: Presumably, the name reflects the fact that in modern urban cities with orthogonal streets, regardless of the straight-line distance between two points, the practical distance is the number of block-sides you must transit to get to your destination...

Velobici: The concept is discussed on detail in the book Taxicab Geometry by Eugene Krause.

You can connect any of the marked points to the center stone with 3 solid, diagonal or one point jump moves, and no less.  

If dx is the horizontal distance, dy the vertical distance, M(dx, dy) the Manhattan distance and C(dx, dy) the "natural connection distance" described above, then C(dx, dy) = ceil(M(dx, dy)/2). Since C(dx, dy) can be obtained from Manhattan distance by halving it and rounding up, the Manhattan distance contains strictly more information than it does. As seen on the board, the C(dx, dy) = 3 circle is the combination of the M(dx, dy) = 5 and M(dx, dy) = 6 circles; one does not lose anything by distinguishing distance twice as finely.

The relation between M and C is easily proved: M(dx, dy) = dx+dy by definition, and C(dx, dy) = min(dx, dy)+ceil(|dx-dy|/2) because it's optimal to use diagonal moves as long as possible, then one-point jumps and finally an extension if needed. Basic arithmetic leads to M(dx, dy) = 2min(dx, dy)+|dx-dy| and ceil(M(dx, dy)/2) = min(dx, dy)+ceil(|dx-dy|/2) = C(dx, dy).