В алгоритме "разделяй и властвуй" ближайшей пары точек, каково значение сортировки "полоски" по значениям y точек?

Question

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

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

Например, вот что говорит " Введение в алгоритмы":

Таким образом, кажется, вы просто берете каждую точку и сравниваете ее со всеми остальными, чтобы найти наиболее близкие точки? Почему тогда нужно сортировать по значению y? У вас уже есть их отсортированные по х, почему бы не грубой силой с этим?

Answer 1

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

Текст объясняет это в разделе " Как мы скоро увидим ".

Сортировка - это оптимизация, которая позволяет перебирать ближайших соседей в O(1) после оплаты расходов на сортировку O(n log n) один раз.