7. Поиск ближайшей пары точек на плоскости.

Задача поиска из множества точек пары, расстояние между которыми минимально решается за O(n^2). Для точек на линии за O(nlogn)(сортируем по порядку за О(logn) и определяем две, расстояние между которыми наименьшее).

Задача близости заключается в поиске пары наиболее близких точек из n штук.

Алгоритм «Разделяй и властвуй»: задачу делим на подзадачи, решаем их и объединяем решения. Глубина деления на подзадачи до того, как подзадачу можно будет решить за константу времени.

1. Сортируем все точки по координате Y. Горизонтальную линию проводим между Yn и Yn+1. Таким образом, разделяем задачу на подзадачи. Если линию провести нельзя (точки лежат на одной горизонтали), то сцену можно повернуть на угол до ?/n+1. Операцию повторяем до того, пока в каждой полосе не останется менее 3-х точек.

2. Для каждой полосы определяем искомую пару точек и расстояние между ними d1 и d2. Выбираем минимальное из d1 и d2, обозначаем d.

3. Проведем горизонтальные линии, отстоящие от разделительной линии на величину d. Получим две параллельные полосы. Точки в полосе упорядочим по горизонтали. Для всех точек, принадлежащих одной из этих полос, рассматриваем прямоугольник величиной d x 2d из другой полосы.

4. Вычисляем длины отрезков из точки А в точки противоположной полосы, причем рассматриваются только точки, принадлежащие соответствующему А прямоугольнику (слева до правой границы прямоугольника). В такой прямоугольник может попасть максимум 6 точек. При анализе точки В рассматриваем шесть уже ранее рассмотренных точек плюс все следующие до правой границы прямоугольника, соответствующего В. (каждая точка из противоположной полосы рассматривается не более 6 раз).

5. Если одно из полученных значений длин отрезков менее d, то заменяем им d и запоминаем соответствующую пару точек.

6. Объединяем решения для более крупных подзадач, повторяя алгоритм с пункта 3.

Время объединения подзадач - O(n), время решения задачи - O(nlogn).