Учитывая список 2d точек, найдите точку, ближайшую ко всем остальным точкам

Input: list of 2d points (x,y) where x and y are integers.

Distance: distance is defined as the Manhattan distance. 
    ie:
    def dist(p1,p2) 
         return abs(p1.x-p2.x) + abs(p1.y - p2.y)

Что такое эффективный алгоритм для нахождения точки, наиболее близкой ко всем остальным точкам.

Я могу думать только о решении грубой силы O (n ^ 2):

minDist=inf
bestPoint = null
for p1 in points:
    dist = 0
    for p2 in points:
        dist+=distance(p1,p2)
    minDist = min(dist,minDist)
    bestPoint = argmin(p1, bestPoint)

в основном посмотрите на каждую пару точек.

 Razor Storm16 окт. 2012 г., 02:01
Ой, я нет означает евклидово расстояние. Я'Я буду редактировать это.
 amit16 окт. 2012 г., 02:00
Это не евклидово расстояние, вам нужно возвести в квадрат (p1.x - p2.x) и (p1.y - p2.y) квадратный корень из суммы. Методdist() это манхэттенские расстояния.

Ответы на вопрос(3)

Начиная с вашего исходного алгоритма, возможна оптимизация:

minDist=inf
bestPoint = null
for p1 in points:
    dist = 0
    for p2 in points:
        dist+=distance(p1,p2)
        //This will weed out bad points rather fast
        if dist>=minDist then continue(p1)
    /*
    //Unnecessary because of new line above
    minDist = min(dist,minDist)
    bestPoint = argmin(p1, bestPoint)
    */
    bestPoint = p1

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

начать цикл p1 с эвристикивнутренний» точка (это создает хорошийminDist во-первых, худшие моменты отбрасываются быстрее)начать p2 петлю с эвристикивнешний» баллы (это делаетdist быстро подниматься, возможно, вызывая условие выхода быстрее

Если вы обменяете размер на скорость, вы можете пойти другим путем:

//assumes points are numbered 0..n
dist[]=int[n+1]; //initialized to 0
for (i=0;i
Решение Вопроса

Обратите внимание, что в 1-D точка, которая минимизирует сумму расстояний до всех точек, является медианой.

В 2-D проблема может быть решена вO(n log n) следующее:

Создайте отсортированный массив x-координат и для каждого элемента в массиве вычислитегоризонтальный» Стоимость выбора этой координаты. Горизонтальная стоимость элемента - это сумма расстояний до всех точек, спроецированных на ось X. Это может быть вычислено в линейное время путем сканирования массива дважды (один раз слева направо и один раз в обратном направлении). Аналогичным образом создайте отсортированный массив y-координат и для каждого элемента в массиве вычислитевертикальный» Стоимость выбора этой координаты.

Теперь для каждой точки в исходном массиве мы можем вычислить общую стоимость для всех остальных точек вO(1) время, добавив горизонтальные и вертикальные затраты. Таким образом, мы можем вычислить оптимальную точку вO(n), Таким образом, общее время работы составляет.O(n log n)

 Razor Storm16 окт. 2012 г., 02:41
Ах да, хорошая мысль.
 krjampani16 окт. 2012 г., 03:00
Я упомянул только медиану как решение для 1-D (что верно). Для двумерного я путешествую через каждую точку и вычисляю расстояние этой точки до всех точек, используя предварительно вычисленные горизонтальные и вертикальные расстояния. Точка, которую я возвращаю, всегда присутствует во входном наборе.
 Razor Storm16 окт. 2012 г., 04:46
Первоначальная проблема состоит в том, чтобы найти точку в наборе, которая является ближайшей к другим наборам. Таким образом, это избавляет от проблемы, когда медиана может не найти оптимальный в случае, когда оптимальный не является частью набора.
 krjampani16 окт. 2012 г., 02:39
Да, в 1-D это можно решить за линейное время. Но в 2-D проблема в том, что точка: (<медиана х-координат>, <медиана Y-координат>) не может быть точкой ввода.
 krjampani16 окт. 2012 г., 02:45
@EugenRieck я нене понимаю, что вы имеете в виду. Я не вычисляю центр масс.
 Alcott02 февр. 2013 г., 12:58
Для начальной части вашего ответа: "в 1-D точка, которая минимизирует сумму расстояний до всех точек, является медианной", я не знаю "Я не совсем понимаю. Зачем?
 krjampani30 сент. 2013 г., 17:51
После того, как мы вычислим и СОХРАНИМ горизонтальные и вертикальные затраты для каждого элемента, для получения общей стоимости точки потребуется всего два постоянных поиска времени.
 Eugen Rieck16 окт. 2012 г., 02:51
Алгоритм, который ищет точку с наименьшей стоимостью с такими понятиями, как медиана, среднее и т. Д., Подразумевает, что средняя / медианная точка является частью набора - это не дано (и пример вызова показывает, что поиск ближайшей точки может быть нетривиальным)
 galactica25 сент. 2013 г., 18:23
Didn»не вижу, как ваш алгоритм сделан в O (nlogn). Основываясь на вашем описании, вы вычисляете горизонтальные / вертикальные затраты для каждого элемента в массиве, это затраты O (n). И есть n таких элементов, что делает O (n ^ 2). Я что-то не так понял?
 krjampani04 февр. 2013 г., 17:35
@Alcott При медиане число точек слева равно количеству точек справа. Предположим, что сумма расстояний до всех точек в медиане равна D. Если вы переместите свое решение на одну точку (расположенное на расстоянии d), тогда ваши затраты станут D + d * (n / 2 + 1) - d * (n / 2-1).
 Eugen Rieck16 окт. 2012 г., 02:42
Это "центр массы" Снова аргумент: необходимо плоское (и плотное) распределение точек
 Razor Storm16 окт. 2012 г., 02:37
Часть, в которой я был уверен, является первоначальным утверждением: «в 1d точка, которая минимизирует сумму расстояний до всех точек, является медианой, Если это действительно так, мы можем решить эту проблему в O (n), используя алгоритм линейного медианного времени.

То, что вы ищете, этоцентр массы.

Вы в основном добавляете все хз и да вместе и разделить будет масса всей системы. Теперь у вас однородная масса меньше частиц, пусть их масса равна 1.

тогда все, что вам нужно сделать, это сложить местоположение частиц и разделить на количество частиц.

скажем, у нас есть p1 (1,2) p2 (1,1) p3 (1,0)

// we sum the x's 

    bestXcord = (1+1+1)/3 = 1

//we sum the y's 

    bestYcord = (2+1)/3 = 1 

так что p2 самый близкий.

решено в O (n)

 Razor Storm16 окт. 2012 г., 02:36
Это решение в основном находит среднее. Средний страдает от скачков выбросов.
 raam8616 окт. 2012 г., 02:33
@EugenRieck Спасибо, что указали на это. Суть вопроса, я думал, что этоs список произвольных точек, таким образом, он может работать большую часть времени.
 raam8616 окт. 2012 г., 02:26
Интуитивно мы ищем средние расстояния. Мы можем пренебречь массой, и мы в основном берем среднее из точечных позиций.
 amit16 окт. 2012 г., 02:19
Не совсем. Центр масс не обязательно должен быть точкой из набора, в то время как в требованиях говорится, что точка, которую вы ищете, должна быть из набора. Например,(0,2),(0,0) - вы не можете выбрать(0,1) как ответ. Я подозреваю, что точка, ближайшая к центру масс, подойдет - но вы можете это доказать?
 amit16 окт. 2012 г., 02:23
Со второй мысли нет - это точно не подойдет. Думать о: .(0,0),(0,0),(0,0),(5000,0),(10000,0)15,000/5=3,000, Ближайший(5000,0) которая сумма расстояний до20000, При выборе (0,0) сумма будет 15000
 lccarrasco16 окт. 2012 г., 02:23
Конечно, еще один проход по набору точек, чтобы найти ближайший кцентр массы" все равно сделал бы это O (n)
 Eugen Rieck16 окт. 2012 г., 02:26
Аргумент центра масс работает только, если у вас есть приблизительно плоское распределение - он ломается, например. на кольцах (крошечная дисперсия в распределении массы делает одну из многих внутренних точек лучшей).
 raam8616 окт. 2012 г., 02:30
Мы все еще можем использовать алгоритм, чтобы взять самую близкую фактическую точку. перебирая точки снова, ищем ближайшее существующее значение.
 raam8616 окт. 2012 г., 02:20
Это не идеально, я согласен. Соотношение оказалось настолько прекрасным, что я должен был выразить это как ответ.

Ваш ответ на вопрос