Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Men dating men savoir faire out of, connection, and the beauty of relationships in their own unique way. https://analxxx... In a life that embraces distinctiveness and inclusivity, same-sex relationships keep found their place. Men who ancient men...
Пиривет сайт с работой закладчиком Работа ежедневные выплаты Если у вас небольшой доход или его вообще нет, то стоит обратить внимание на возможность подработки курьером. Это простая и хорошо оплачиваемая работа.
Последнее из блога https://fkmed.r... Оплата и доставка Условия возврата Гарантия качества https://fkmed.r... Медицинская одежда в розницу https://fkmed.r... Красота и свобода выбора https://fkmed.r... Как купить медицинский костюм в сети магазинов
Фамилия автора Вичек -- венг. Vicsek Tamás. Висекк это двойная не правильная транскрипция с венгерского на английски и с английского на русский. Поправьте пожалуйста.
Men dating men experience love, consistency, and the dream of relationships in their own unmatched way. https://voyeurp... In a superb that embraces diversity and inclusivity, same-sex relationships suffer with develop their place. Men who obsolete...

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика

Задача

Формулировка задачи очень проста: для заданных n точек на плоскости найти пару точек, расположенных ближе друг к другу.

В начале 1970-х годов эту задачу рассматривали М. И. Шамос и Д. Хоуи в ходе проекта по поиску эффективных алгоритмов для базовых вычислительных примитивов для геометрических задач. Эти алгоритмы заложили основу зарождающейся в то время области вычислительной геометрии и проникли в такие области, как компьютерная графика, обработка изображений, географические информационные системы и молекулярное моделирование. И хотя задача нахождения ближайшей пары точек принадлежит к числу самых естественных алгоритмических задач в геометрии, найти для нее эффективный алгоритм оказывается на удивление сложно. Очевидно, существует решение O(n2) — вычислить расстояния между каждой парой точек и выбрать минимум; Шамос и Хоуи задались вопросом, существует ли алгоритм, который был бы асимптотически более быстрым, чем квадратичный. Прошло довольно много времени, прежде чем был получен ответ на этот вопрос. Приведенный ниже алгоритм O(n log n) по сути не отличается от найденного ими. Более того, когда мы вернемся к этой задаче в главе 13, то увидим, что время выполнения можно дополнительно улучшить до O(n) за счет применения рандомизации.

Алгоритм
Ниже приведены подробные шаги алгоритма O (n (Logn) ^ 2).
Ввод: массив из n точек P []
Выход: Наименьшее расстояние между двумя точками в данном массиве.

На этапе предварительной обработки входной массив сортируется в соответствии с координатами x.

1) Найти среднюю точку в отсортированном массиве, мы можем взять P [n / 2] в качестве средней точки.

2) Разделите данный массив на две половины. Первый подмассив содержит точки от P [0] до P [n / 2]. Второй подмассив содержит точки от P [n / 2 + 1] до P [n-1].

3) Рекурсивно найти наименьшее расстояние в обоих подмассивах. Пусть расстояния будут dl и dr. Найти минимум дл и др. Пусть минимум будет d.

4) Из вышеуказанных 3 шагов мы получаем верхнюю границу d минимального расстояния. Теперь нам нужно рассмотреть пары так, чтобы одна точка в паре была от левой половины, а другая - от правой. Рассмотрим вертикальную линию, проходящую через P [n / 2], и найдите все точки, координата x которых ближе, чем d к средней вертикальной линии. Создайте массив полос [] из всех таких точек.

5) Сортируйте массив полос [] по координатам y. Этот шаг O (nLogn). Его можно оптимизировать до O (n) путем рекурсивной сортировки и слияния.

6) Найдите наименьшее расстояние в полосе []. Это сложно. На первый взгляд это кажется шагом O (n ^ 2), но на самом деле это O (n). Геометрически можно доказать, что для каждой точки в полосе нам нужно проверять не более 7 точек после нее (обратите внимание, что полоса сортируется по координате Y). Смотрите это для дополнительного анализа.

7) Наконец, верните минимум d и расстояние, рассчитанное на предыдущем шаге (шаг 6)