tgoop.com/the_algorithms/4673
Last Update:
Ближайшая пара точек с использованием алгоритма «Разделяй и властвуй»
Алгоритм, используемый для поиска двух ближайших друг к другу точек в наборе точек двумерного пространства. Другими словами, он вычисляет минимальное расстояние между любыми двумя точками в заданном наборе.
Алгоритм:
1. Найдите среднюю точку, которая равна P[n/2].
2. Разделите массив на две половины: от P[0] до P[n/2] и от P[n/2+1] до P[n-1].
3. Рекурсивно находим минимальные расстояния в обеих половинах, получая dl и dr.
4. Пусть d будет минимумом dl и dr.
5. Создайте массив «полосы», содержащий точки ближе, чем d к средней вертикальной линии, и отсортируйте его по координатам y.
6. Найдите наименьшее расстояние в массиве полос, рассматривая не более 7 точек после каждой точки.
7. Верните минимум d и расстояние, найденное на шаге 6, как ближайшую пару точек.
Сложность: O(n (Logn)^2)
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4673