Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Р (N, 2) = 2Р {N12, 2) + О {N) = О (N log N). (5.1)
На основании этого соотношения получаем теорему 5.3:
Теорема 5.3. Кратчайшее расстояние, определяемое N точками на плоскости, может быть найдено за время Q{N\ogN) и является оптимальным.
Главные особенности описанного подхода на основе метода «разделяй и властвуй», обеспечивающие возможность его обобщения на случай более высокой размерности, приведены ниже:
1. Шаг, на котором происходит объединение решений подзадач, производится в пространстве на единицу меньшей размерности (от плоскости переходим к прямой).
2. Два множества точек, объединяемые после решения подзадач, обладают свойством разреженности, т. е. для каждого из множеств справедливо условие: расстояние между любыми двумя точками не может быть меньше некоторой заданной константы. Свойство разреженности имеет ключевое значение для шага объединения решений. Введем формальное определение.
Определение 5.1. Пусть заданы действительное число б > 0 и целое число с ^ 1. Для заданного б множество точек S в d-мер-
') При анализе нерекурсивной реализации этого алгоритма, разработанной Хоуи и Шеймосом, была обнаружена любопытная ситуация: число выполняемых вычислений расстояния всегда было строго меньше N. Далее в этом разделе будет показано, что это имеет место всегда. Конечно, время работы алгоритма по-прежнему определяется шагом сортировки.
244
Г л. 5. Близость: основные алгоритмы
ном пространстве имеет разреженность с, если любой гиперкуб со стороной 26 содержит не более с точек множества S.
Здесь разреженность определяется как (монотонная неубывающая) функция от 6. Как будет показано, разреженность можно ввести, взяв в качестве 6 минимальное расстояние между парами точек. Как видно из рис. 5.12, в рассматриваемом случае множество точек, находящихся на расстоянии не более 6 от разделяющей прямой /, является разреженным и при этом с = 12. (Заметим, что с = 12 = 4X3 для d = 2.)
В случае d ;=s 2 часть пространства Ей, заключенная между двумя гиперплоскостями, ортогональными одной из координат-
при ортогональном проецировании 26, содержащий ровно СТОЛЬКО (прий>2). же точек, сколько и исходный
куб (рис. 5.13). Предположим теперь, что в Ed задано множество S, содержащее N точек. По рассмотренной схеме, приведем следующий алгоритм:
procedure BnAPAd(S)
1. Выбрав подходящим образом гиперплоскость / (называемую разделяющей гиперплоскостью), ортогональную одной из координатных осей, разбить множество S на два подмножества S] и S2 (затратив на это время O(N)), содержащих соответственно aN и (1 — а) N точек (где 0 < а0 а ^ 1 — <хо будет определено далее).
2. Рекурсивно применить алгоритм к множествам Si и S2, получив минимальные расстояния 6i и 82 между точками в множествах Si и S2 соответственно. Положить 6 = min(6i, 62).
3. Объединить полученные результаты, выполнив обработку точек, попавших в 6-слой пространства Ей, имеющий ширину 26 и разделяемый гиперплоскостью / пополам.
Рассмотрим более подробно шаг 3 алгоритма. В качестве рабочей гипотезы предположим, что множество точек в 6-слое, обо-
Рис. 5.13. Свойство разреженности множества точек сохраняется
ных осей и удаленных друг от друга на расстояние 26, называется 8-слоем. Заметим, что, если разреженность 6-слоя при заданном 6 равна с, эта разреженность сохраняется при проецировании 6-слоя на гиперплоскость, делящую 6-слой пополам ((d — — 1) -мерное многообразие). Действительно d-мерный куб со стороной 26 проецируется в (d— 1)-мерный куб также со стороной
5.4. Решение задачи о ближайшей паре
245
значаемое Si2, имеет разреженность с при заданном 6 (позднее мы убедимся, что такое с существует). Обозначим через S*l2 проекцию множества Si2 на гиперплоскость / ((d—1)-мерное пространство). Очевидно, что необходимым условием для того, чтобы пара точек из Sj2 была ближайшей парой в множестве S, является следующее: расстояние между проекциями этих точек на гиперплоскость / не должно превышать б. Таким образом, имеется разреженное множество S*l2, в котором необходимо найти все пары точек, удаленных друг от друга на расстояние, не превышающее некоторую величину (<6). Это составляет предмет следующей задачи, представляющей самостоятельный интерес.
Задача Б.7 (ПОИСК БЛИЖАЙШИХ СОСЕДЕЙ В ОКРЕСТНОСТИ ФИКСИРОВАННОГО РАДИУСА В РАЗРЕЖЕННОМ МНОЖЕСТВЕ). Пусть заданы действительное число б и множество из М точек в Еа, имеющее разреженность с для заданного б. Требуется перечислить все нары точек, расстояние между которыми меньше б.
Полагая | S*21 = М и обозначив через F6j С(М, d) время решения задачи Б.7, на основании проведенного анализа получаем следующее рекуррентное соотношение:
P(N, d) = P(aN, d) + P((l -a)N,d) + 0{N) + F6>c(M, d-l).
(5.2)
Наша цель заключается в минимизации F6lC(M, d—l). Это достигается как за счет выбора разделяющей гиперплоскости, минимизирующей М, так и за счет разработки эффективного алгоритма решения задачи Б.7. Обе эти подцели достижимы благодаря следующей интересной теореме:
