Нахождение максимального расстояния между (x, y) координатами - PullRequest
Новая
       4

Нахождение максимального расстояния между (x, y) координатами

6 голосов
/ 04 ноября 2011

Я пытаюсь вычислить максимальное манхэттенское расстояние большого двумерного входа, входы состоят из (x, y) s, и я хочу вычислить максимальное расстояние между этими координатами в O меньше чем n (n ^ 2) время, я могу сделать это в O (n ^ 2), пройдя все элементы, например:
* (Манхэттенское расстояние между двумя точками (X1, Y1) и (X2, Y2) равно: | X1-X2 | + | Y1-Y2 |) 

for ( 0 -> n )  
   for ( 0-> n )   
       { // here i calculate |Xi - Xj| + |Yi - Yj| which is maximum }

, но он не будет работать эффективно для очень больших входов: (
У кого-нибудь есть идеи для лучшего алгоритма?

Ответы [ 5 ]

14 голосов
/ 04 ноября 2011

Можно рассмотреть только два случая, если мы рассмотрим только такие результаты, что Xi <= Xj.

  • Если Yi <= Yj, то расстояние равно (Xj + Yj) - (Xi + Yi)
  • В противном случае расстояние составляет (Xj - Yj) - (Xi - Yi)

Разобрав его на эти случаи, я избавился от функции абсолютного значения, которая значительно упрощает анализ расстояний.

Итак, мы просто выбираем точки с минимальным и максимальным x+y и вычисляем расстояние. Затем выберите точки с минимальным и максимальным значениями x-y и вычислите расстояние. Одно из этих двух расстояний - ваш максимум.

Это можно сделать в O(n), что является асимптотически оптимальным.

9 голосов
/ 04 ноября 2011

Это довольно просто и может быть рассчитано в O(n)

Пусть x1>x2 и y1>y2

max(|x1-x2|+|y1-y2|) = max(x1-x2+y1-y2) = max(x1+y1) - min(x2+y2)

Пусть x1>x2 и y1<y2

max(|x1-x2|+|y1-y2|) = max(x1-x2-y1+y2) = max(x1-y1) - min(x2-y2)

Теперь измените x1 на x2, и вы получите те же результаты.

Итак, в общем, ваше решение 

max ( (max(xi+yi)-min(xi+yi)), (max(xi-yi) - min(xi-yi)) )
2 голосов
/ 04 ноября 2011

Лучшее, что можно сделать с подобными вопросами, - это попытаться получить небольшие результаты, которые помогут вам решить общую проблему.

Например, не сложно определить, что для любых трех пунктов,A, B и C, которые имеют условие, что B составляет между (подробнее об этом в секунду), A и C, B никогда не будут дальше от четвертой точки D, чем одна из A и C.стандартная евклидова метрика расстояния, точка находится между двумя другими точками, если она лежит на соединяющем их отрезке.Для манхэттенских измерений это не так просто - отчасти потому, что концепция сегмента не так хорошо понятна.

Более общий способ описания «между» заключается в следующем (используя обозначение, что расстояние от А до Вis | AB |): точка B находится между двумя точками A, C, если | AB |+ | BC |= | AC |

Вы можете видеть, что на евклидовом расстоянии это означает, что B лежит на отрезке, соединяющем A и C.

На манхэттенском расстоянии это означает, что точка B содержится впрямоугольник, определенный A и C (который, конечно, может быть прямым отрезком, если AC параллелен одной из осей).

Этот результат означает, что для любой точки, если она лежит между двумя существующими точками, она может бытьне дальше от каких-либо новых точек, добавленных к набору, кроме двух, которые его окружают.

Теперь эта информация не решает проблему для вас, но позволяет отбросить многие потенциальные будущие вычисления.Как только вы определили, что точка находится между двумя другими, нет смысла отслеживать ее.

Итак, вы можете решить эту проблему, отслеживая только самые крайние точки и игнорируя любые, попадающие в них.

Интересное упражнение для случайного наблюдателя

Докажите, что у вас может быть не более 4 разных точек, так что ни одна из точек не находится между двумя другими, вМанхэттенское чувство.

С этим вторым результатом становится ясно, что вам нужно будет отслеживать только 4 балла.

Некоторые из уже представленных методов, вероятно, быстрее,но этот способ веселее!

Дополнительный кредит

Обобщите эти идеи до n измерений

0 голосов
/ 04 ноября 2011

первое большое улучшение будет: 

for ( X: 0 -> n )
    for ( Y: X -> n )
        { compute the distance between X and Y }

, поскольку расстояние между X и Y такое же, как расстояние между Y и X., которое сократило бы ваши вычисления наполовину ...

0 голосов
/ 04 ноября 2011

Максимальное расстояние будет между наиболее удаленными друг от друга точками.Так что вам нужно найти точку с максимальным X и максимальным Y, а затем найти точку с минимальным X и минимальным Y и рассчитать расстояние между ними.Может быть много точек, которые соответствуют критериям ... но, по крайней мере, у вас будет гораздо меньше очков для проверки

...