FeiWuLiuZiao's blog

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

just curious

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

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

And is there a Euclidean Distance MST algo

→ Reply
»
85 minutes 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
  • »
    »
    65 minutes ago, # ^ |
      Vote: I like it 0 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