0

I overheard someone talking about using the Manhattan metric against nodes on an arbitrary graph (or even a tree). At the time, I didn't think much of it, but having dwelled upon it, does it even make sense?

Clearly, said graph would need to be mapped on to an appropriate space (i.e., $\mathbb{Z}\times\mathbb{Z}$) in a lattice-like fashion. However, wouldn't this preclude the graph from having more than four edges for any particular vertex?

Does it work if you 'latticify' the graph in to $\mathbb{Z}^n$, where $n=\frac{1}{2}\max (\textrm{#edges per vertex})$ -- or something like that -- and likewise extend the metric into $n$-dimensions?

wlad
  • 8,185
Xophmeister
  • 477
  • 2
    Wouldn't the Manhatten metric simply mean that the distance between two vertices is the minimal number of edges for a path between them? – Hagen von Eitzen May 27 '15 at 20:30
  • 1
    @HagenvonEitzen, in finding paths between two cities for driving, an algorithm that uses the embedding of the graph in a metric space (the Earth) is the A* algorithm. Books by Norvig and, early, Judea Pearl. Altering the metric in the ambient space somewhat alters the algorithm, http://en.wikipedia.org/wiki/A*_search_algorithm – Will Jagy May 27 '15 at 20:46
  • @HagenvonEitzen Yes, I suppose it does :) I was thinking too quantitatively; hence trying to force the graph into $\mathbb{Z}^n$... If you submit your comment as an answer, I'll accept it. – Xophmeister May 28 '15 at 08:53

0 Answers0