Минимизация максимального Манхэттен расстояние от точки до множества точек

Question

В течение 3 точек в 2D:

P1(x1,y1), 
P2(x2,y2), 
P3(x3,y3) 

мне нужно найти точку P(x,y), таким образом, что максимум расстояний MANHATTAN

max(dist(P,P1), 
    dist(P,P2), 
    dist(P,P3)) 

будет минимальным.

Любые идеи об алгоритме?

Я бы предпочел бы точный алгоритм.

Answer 1

Существует точный, нетериративный алгоритм проблемы; как указал Кноте, the Manhattan distance is rotationally equivalent to the Chebyshev distance, а P тривиально вычислим для чебышевского расстояния как среднее из крайних координат.

Точки достижимой из Р в пределах Манхэттенского расстояния х образует ромб вокруг P. Таким образом, нам нужно найти минимальный алмаз, который охватывает все точки, и ее центр будет P.

Если мы повернем координатные система на 45 градусов, бриллиант - квадрат. Поэтому проблему можно свести к нахождению наименьшего квадрата окружности точек.

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

Так, в алгоритмической форме:

1. вращать и масштабировать систему координат путем присвоения х '= х/SQRT (2) - г/SQRT (2), у' = х/SQRT (2) + y/sqrt (2)
2. Вычисление x'_c = (max (x'_i) + min (x'_i))/2, y'_c = (max (y'_i) + min (y'_i))/2
3. Поверните назад с помощью x_c = x'_c/sqrt (2) + y'_c/sqrt (2), y_c = - x'_c/sqrt (2) + y'_c/sqrt (2)

Затем x_c и y_c дают координаты P.

Answer 2

Если приблизительное решение в порядке, вы можете попробовать простой алгоритм оптимизации. Вот пример, в Python

import random 
def opt(*points): 
    best, dist = (0, 0), 99999999 
    for i in range(10000): 
     new = best[0] + random.gauss(0, .5), best[1] + random.gauss(0, .5) 
     dist_new = max(abs(new[0] - qx) + abs(new[1] - qy) for qx, qy in points) 
     if dist_new < dist: 
      best, dist = new, dist_new 
      print new, dist_new 
    return best, dist 

Пояснение: Мы начинаем с точки (0, 0), или любой другой случайной точки, и изменить его в несколько тысяч раз, каждый раз сохраняя лучшее из нового и ранее лучший пункт. Постепенно это будет приближать оптимальный.

Примечание, что просто выбирая среднее или медиану трех точек, или решения по х и у независимо друг от друга делает не работу при минимизации максимальное расстояние Манхэттен. Противопоставление: рассмотрите точки (0,0), (0,20) и (10,10) или (0,0), (0,1) и (0,100). Если мы выберем среднее из наиболее разделенных точек, это даст (10,5) для первого примера, и если мы возьмем медиану, это будет (0,1) для второго примера, у которого оба имеют более высокий максимум Манхэттен расстояние, чем оптимальный.

Update: Похоже, решение для х и у независимо друг от друга и, взяв среднее из самых отдаленных точек делает на самом деле работы, при условии, что один делает некоторые пред- и постобработки, как отметил thiton.