Я вважаю, що я розумію алгоритмчітко, крім кроку, на якому ви дивитеся, щоб побачити, чи є будь-які точки, які знаходяться поруч, переглядаючи розділ і створюючи смугу, де точки в смузі є кандидатами.
Але потім алгоритм стверджує, щоб відсортувати точкиза їх координатами y, а потім перевіряйте кожну іншу точку смуги, щоб знайти, якщо є менша відстань, ніж знайдена раніше. Це в основному звучить, як ви грубої сили в смузі.
Наприклад, ось що Введення в алгоритми стверджує:
Так, здається, ви просто берете кожну точку і порівнюєтеце проти всіх інших знайти найближчі точки? Чому тоді необхідно сортувати за значенням y? Ви вже відсортували їх по x, чому б не грубість?
Відповіді:
1 для відповіді № 1Ви не порівнюєте грубу силу з усіма точками в Y" але тільки проти одного поруч p. Якщо це вже дуже далеко, то можнапросто зупиніться, тому що всі інші точки будуть ще далі. Ви продовжуєте оцінювати наступного найближчого сусіда, якщо останній все ще перебував у межах відстані пошуку.
Текст пояснює його в Як ми побачимо найближчим часом розділ
Сортування - це оптимізація, яка дає змогу перейти до найближчих сусідів O(1) після сплати витрат на сортування O(n log n) один раз