3
$\begingroup$

Who came up with the name "Manhattan distance" (for the distance between two points as measured by the sum of the horizontal and vertical distances, as opposed to the length of the straight line between them)?

illustration of Manhattan and Euclidean distance

$\endgroup$
8
  • $\begingroup$ Google ngrams suggests the first use of the term "Manhattan distance" occurs in 1963 in Proceedings of the 1962 Workshop on Computer Organization. $\endgroup$
    – NWR
    Mar 2 at 18:47
  • 1
    $\begingroup$ For what it's worth, it's mentioned on p. 377 of Random minimal trees by E. N. Gilbert (1965) in a way that strongly suggests the term was already in use then. Perhaps something more historically informative can be found in a footnote or comment in one of the references to this paper (many of which I don't have access to, so someone with university access might want to investigate). My guess is that the notion arose in traffic engineering literature after WW 2 as a concrete (and obvious) notion, (continued) $\endgroup$ Mar 2 at 18:54
  • 1
    $\begingroup$ and somewhat later the name was used by more mathematically inclined authors who knew it was an actual metric, one that had been around for several decades. In fact, even before the notion of a metric space arose (around 1905), analysis proofs involving several variables made use of estimates involving this metric, since it's easier to work with $|x_2-x_1| + |y_2-y_1|$ than with $\sqrt{|x_2-x_1|^2 + |y_2-y_1|^2},$ and bounds on the values of the former immediately lead to nearly the same bounds on the latter (within a factor of $2$ I think, if not even better). $\endgroup$ Mar 2 at 18:54
  • $\begingroup$ My guess is that the notion arose in traffic engineering literature --- Oops, this should have been "the name arose". The notion, even as a specific mathematical metric, had been around for decades before this. $\endgroup$ Mar 2 at 19:03
  • $\begingroup$ @DaveLRenfro Why WWII? The Manhattan grid system dates to 1811. (Though, even today, the grid doesn't cover the whole island - the southern tip is a mess, and Broadway cuts across the whole island at an angle) $\endgroup$ Mar 2 at 19:06
5
$\begingroup$

I am capturing information from a comment as a starting point for a community wiki answer to which others can add earlier citations.

Harvey L. Garner and Jon S. Squire, "Iterative Circuit Computers", in Proceedings of the 1962 Workshop on Computer Organization, Baltimore, 1962, pp. 156-181. (Google scan). On page 165:

$W(p)$ is the number of distinct pairs of modules at Manhattan distance, $p$, and does not refer to the number of ways of connecting a pair of modules.

The paper is about a computer arranged as a two-dimensional grid of tiles, which explains the use of Manhattan distance. The term is not explained anywhere in the paper, so its use appears to have been well established by 1962.

By collating many overlapping snippets from Google's snippet view, I was able to extract the following quotation from a document dating to the same year that explains the term:

Rodolfo Gonzales and Sandra Palais, "A Path-Building Procedure for Iterative Circuit Computers", University of Michigan Information System Laboratory Technical Note, 1962. On page 22:

[...] two senses are to be followed when tracing the segments in each of the horizontal and vertical directions. This means that once the vertical and horizontal priorities are established, for example vertical down and horizontal to the right, all the path segments have to be traced in either of the two specified senses exclusively. It is to be noted that this restriction on the allowable class of paths has the advantage of eliminating the need for an algorithm capable of tracing a minimum length path, since all non-regressive paths have the same length when measured in terms of the number of segments needed to connect the modules. This method of measuring distance has been called "Manhattan distance."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.