Проблемы с пониманием алгоритма «разделяй и властвуй» в ближайшей паре

Question

Я новичок в кодировании, и сегодня я выполнил тривиальное решение проблемы ближайшей пары в двумерном пространстве. (2 для циклов)

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

Что я понимаю: -> Сначала мы разбиваем массив на 2 половины и сортируем все только с учетом координат X , Это можно сделать в n log n.

Далее идут рекурсивные вызовы, которые «находят две точки с наименьшим расстоянием» в каждой половине. Но как это сделать точно ниже O (n ^ 2)? В моем понимании невозможно найти наименьшее расстояние между N / 2 точками без проверки каждой из них.

В 1-D есть решение, которое для меня абсолютно логично. После сортировки мы знаем, что расстояние между двумя несмежными точками не может быть меньше расстояния не менее двух смежных точек. Однако это не так для двумерного пространства, так как у нас есть дополнительная координата Y, которая может привести к наименьшему расстоянию между двумя точками, не смежными по оси X.

Answer 1

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

Однако вот несколько идей для начала интуиции:

1. (Структура рекурсии) Вопрос гласит:

   Далее идут рекурсивные вызовы, которые "находят две точки с наименьшим расстоянием" в каждой половине. Но как это сделать точно ниже O (n ^ 2)? В моем понимании невозможно найти наименьшее расстояние между N / 2 точками, не проверив каждую из них.

   Однако рекурсия не останавливается на уровне 1 - предположим, ради аргумент, что какой-то O(n log n) алгоритм работает. Нахождение ближайших пар среди N/2 точек с применением этого алгоритма занимает O(N/2 log N/2), а не O((N/2)^2).

2. (Последствия нахождения ближайшей пары в половине)
   Если вы нашли ближайшую пару (p, q) в «левой» половине набора точек, расстояние этой пары устанавливает верхнюю границу ширины коридора вокруг линии деления пополам, от которой более близкая пара (r, s) с r от слева, s с правой половины можно нарисовать. Если ближайшее найденное расстояние является «маленьким», это значительно уменьшает размер набора кандидатов. Поскольку точки упорядочены по их координате x, алгоритм может эффективно использовать информацию. Указанный коридор может по-прежнему охватывать весь набор N точек, но если он это делает, он предоставляет информацию о геометрии набора точек: точки каждой половины будут в основном выровнены вдоль вертикальной линии. Эту информацию можно использовать алгоритмически - самый наивный способ - это выполнить алгоритм еще раз, но с сортировкой по y координатам и делением пополам точки, заданной горизонтальной линией. Обратите внимание, что выполнение любого алгоритма постоянное число раз не меняет асимптотику c времени выполнения, выраженную в записи O(.).

3. (Поиск близкой пары с одной точкой от каждой половины )
   Подумайте о проверке пары точек (r, s), по одной точке от каждой половины. Известно, что разница в их x и y координатах, соответственно, не должна превышать минимальное расстояние d, найденное до сих пор. Из рекурсии известно, что не может быть точек r', s' (r' слева, s' справа), ближе к r, s, соответственно, чем d. Таким образом, учитывая, что r не может быть 'много' кандидатов из другой половины.
   Представьте круг радиуса d, нарисованный вокруг r. Любая точка s от другой половины, находящаяся ближе, чем d, должна находиться внутри этого круга. Пусть их будет несколько - однако минимальное расстояние между каждой парой все равно будет не менее d. Максимальное количество точек, которые могут быть распределены внутри круга радиуса d, так что расстояние между каждой их парой не менее d равно 7 - представьте себе правильный шестиугольник с длиной стороны d и центром, совпадающим с центр круга. Таким образом, после рекурсии, самое большее, каждый r из левой половины должен проверяться при максимальном постоянном количестве точек от другой половины, что составляет часть алгоритма после выполнения рекурсии в O(N).
   Обратите внимание, что поиск кандидатов в пары для заданного r является эффективной операцией - точки с обеих половин были отсортированы по одному и тому же критерию.