FeiWuLiuZiao's blog

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

just curious

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

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

And is there a Euclidean Distance MST algo

→ Reply
»
11 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
  • »
    »
    10 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
  • »
    »
    71 minute(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    link is a tree that every node has a degree of 2, except the root and the only leaf

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

Depending on context, you may also be interested in the rectilinear Steiner tree problem.

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

Yes, you can do it in O(n lgn) by only creating edges between one point and the closest point to it in each of 8 octants around it, then running normal MST algo on it.

→ Reply
  • »
    »
    71 minute(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i know how to do manhattan distance MST, im asking about link

    → Reply