Самый быстрый способ найти минимальное расстояние между точками

Question

У меня есть набор 2D точек, и мне нужно найти самый быстрый способ выяснить, какая пара точек имеет наименьшее расстояние в наборе.

Каков оптимальный способ сделать это? Мой подход состоит в том, чтобы отсортировать их с помощью быстрой сортировки, а затем рассчитать расстояния. Это будет O (nlogn + n) = O (nlogn).

Можно ли сделать это за линейное время?

Спасибо.

Answer 1

Это на самом деле :

Задача ближайшей пары точек или задача ближайшей пары - это проблема вычислительной геометрии : дано n точек в метрическом пространстве найти пару точек с наименьшим расстоянием между ними ...

В вычислительной модели, которая предполагает, что функция floor вычисляется в постоянном времени, проблема может быть решена за O ( n log log n ) времени , Если мы позволим использовать рандомизацию вместе с функцией этажа, проблема может быть решена за O ( n ) времени.

Answer 2

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

Answer 3

Нет. Минимальное расстояние между ВСЕМИ точками в O ( n ^ 2), потому что вы должны сравнивать каждую точку с любой другой точкой. Технически это n * n / 2, потому что нужно заполнить только половину матрицы.

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