FeiWuLiuZiao's blog

Is there a Manhattan Distance Minimum Spanning Link algorithm, or is it NPC
By FeiWuLiuZiao, history, 13 hours ago, In English

just curious

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
13 hours ago, # |
  Vote: I like it +15 Vote: I do not like it

And is there a Euclidean Distance MST algo

→ Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

What is a minimum spanning link? Is it a minimum spanning tree? If yes, then you can use any minimum spanning tree algorithm and just use the manhatten distances or the euclidean distances as the edge weights.

→ Reply
  • »
    »
    5 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I believe the interesting question is whether it's possible to do it faster than O(n^2) due to the need to calculate distance between every pair of points, to which the following links may be useful:

    manhattan

    euclidean

    → Reply