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

Question

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

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

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

?

Answer 1

Рассматривать только два случая, если мы рассматриваем только такие результаты, что .

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

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

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

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

Answer 2

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

Answer 3

первый большой шаг вперед будет:

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

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

Answer 4

Это довольно просто и может быть вычислена в 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))) 

Answer 5

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

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

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

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

В Manhattan расстояния, это означает, что точка В, содержится в прямоугольнике, определенном А и С (который конечно, может быть прямым сегментом, если АС параллельна одной из осей).

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

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

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

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

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

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

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

Extra Credit

Обобщить эти идеи п размеров