Ближайшая пара точек

[qx87]

Задача поиска двух ближайших точек из данного набора может быть решена с помощью стратегии "разделяй и властвуй" за время $O(n \log n)$. Описание этого алгоритма (на английском) можно поглядеть здесь (pdf).

Ключевой момент алгоритма состоит в том, что на прямоугольнике $\delta \times {\delta \over 2}$ можно расположить не более 6 точек так, чтобы расстояние между любыми двумя из них не превышало $\delta$. Поэтому в отсортированном массиве точек проверяются расстояния от каждой точки только до пяти последующих.

Но расположить шесть точек можно лишь единственным образом: вот так. И в этом случае минимальное расстояние между точками будет в точности равно $\delta$. Но ведь $\delta$ определена как минимальное найденное на данный момент расстояние. Следовательно, нам нужно искать лишь расстояния, строго меньшие, чем $\delta$. Значит, в алгоритме достаточно проверять не далее четырёх точек от текущей.

Я прав? Если нет, то где ошибка? Если да, то почему везде в Интернете предлагают проверять 5 (а то и даже 7) точек?

[Pavia]

Цитата:

Следовательно, нам нужно искать лишь расстояния, строго меньшие, чем . Значит, в алгоритме достаточно проверять не далее четырёх точек от текущей.

Если ты возьмёшь 4 то есть вероятность что они будут располагаться в углах четырёх угольника, когда как минимальная эта та, что на стороне.
Как ты определишь какая точка где располагается не проверяя их все?
Можно проверить 5 и методом исключения найти 6. Хотя точи с минимальным расстоянием мы так и определим, но расстояние не вычислили, так что по любому надо вычислять расстояние для всех 6 точек.

[qx87]

Pavia в сообщении #704212 писал(а):

Как ты определишь какая точка где располагается не проверяя их все?

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

Я говорю о том, что если даже все последующие 5 точек и лежат в данном прямоугольнике (вместе с текущей, то есть всего 6 штук), то расстояния, меньшего чем $\delta$, мы среди них не найдём. Поэтому есть смысл проверять только 4 точки.

[Pavia]

qx87 в сообщении #704218 писал(а):

Поэтому есть смысл проверять только 4 точки.

Да всё верно. Только эти точки из множества $S_2$, а в массиве у тебя точки из $S_2$ и $S_1$, что
в сумме даёт 8 точек из которых одна $P$. Итого 7 точек. Разумеется те 3 проверять не нужно они и так проверены, но тут опять вопрос. Как отличить кто из какого множества? Самое простое не разбирать, а проверять всех из общей "кучи". т.е все 7 точек

http://algolist.manual.ru/maths/geom/closest_points.php