Блог пользователя FeiWuLiuZiao

Is there a Manhattan Distance Minimum Spanning Link algorithm, or is it NPC
Автор FeiWuLiuZiao, история, 9 часов назад, По-английски

just curious

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 часов назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

And is there a Euclidean Distance MST algo

→ Ответить
»
65 минут назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    45 минут назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить