Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Таким образом, мы получили разреженное множество S\2, мощность которого не превосходит cdNl~l/d (с разреженностью c = 4-3d-' для вычисленного б). Затем решаем задачу Б.7 для множества 5*2, являющегося проекцией множества Sl2 на полученную ранее разделяющую гиперплоскость /. Для этой задачи, имеющей размерность d—1, вновь применяется метод «разделяй и властвуй». В частности, ищется разделяющая гиперплоскость /', существование которой гарантируется теоремой 5.4, при этом 6 считается заданным (каким оно получено на шаге 2 процедуры БПАРАсО, а с равна разреженности множества S]2, только что полученной нами. Отсюда следует, что мощность множества точек в б-слое около разделяющей гиперплоскости /' ограничена величиной (d— 1) • сМ1-1Л<*-,>, т. е. о(М). В заключение решается задача Б.7, имеющая размерность d—l, для чего приходится определять разделяющую гиперплоскость, затратив на это время О(М), после чего рекурсивно решать две аналогичные задачи на множествах с мощностью аМ и (1 —
S.5. Решение задач о близости методом локусов
249
— а)М, и наконец решается задача, имеющая размерность d— 2 на множестве мощностью о(М). Это дает следующее рекуррентное соотношение:
F6tC(M, d-l) = F6,e{^,d-l)+Ft,e(M(l-^), d-l) +
+ 0(M) + F6>c(o(M), d-2). (5.3)
Легко убедиться, что это соотношение имеет решение Ft,c{M,d—1) = 0(М logAl). Этот факт интересен сам по себе, чтобы представить его в виде следующей теоремы:
Теорема 5.5. В разреженном множестве из М точек в Е'1 (с разреженностью с для заданного 6) все пары, точек, расстояния между которыми меньше 6, можно найти за время 0(М logAl).
Возвращаясь к исходной задаче о ближайшей паре, напомним, что М — это мощность множества Su, равная в силу способа построения 0(A/1-1/d), т. е. o(N\\ogN). Отсюда следует, что E&,c(M,d—1) = 0(М logAl) = O(N). И как следствие, рекуррентное соотношение (5.2) имеет решение Р (N, й) — = 0(NlogN). Таким образом, время выполнения основных вычислений совпадает по порядку с временем, затрачиваемым на предварительную сортировку. В результате получаем следующую теорему:
Теорема 5.6. Ближайшая пара множеств из N точек в Еа может быть определена за время Q(N\ogN), что является оптимальным.
5.5. Решение задач о близости методом локусов; диаграмма Вороного
Хотя использование метода «разделяй и властвуй» при решении задачи о ближайшей паре выглядит довольно обнадеживающе, но уже при решении задачи ВСЕ БЛИЖАЙШИЕ СОСЕДИ, являющейся на первый взгляд лишь простым обобщением задачи о ближайшей паре, это метод оказывается неприемлемым. Действительно, если попытаться аналогичным образом использовать для решения задачи ВСЕ БЛИЖАЙШИЕ СОСЕДИ рекурсию, то обнаружится, что при естественном способе разбиения на подзадачи свойство разреженности уже не имеет места и при этом не видно способа выполнить шаг слияния быстрее, чем за квадратичное время. С другой стороны, довольно ценный эвристический прием, используемый при разработке геометрических алгоритмов, состоит в том, чтобы выделить области точек, обладающие требуемым свойством
250
Гл. 5. Близость: основные алгоритмы
(локусы), и попытаться организовать их в виде некоторой структуры данных. Так, в случае плоскости мы хотим решить следующую задачу:
Задача Б.8 (ОБЛАСТИ БЛИЗОСТИ). На плоскости задано множество S, содержащее N точек. Требуется для каждой точки pi множества S определить локус точек (х, у) на пло-, скости, для которых рас-
стояние до pi меньше, . чем до любой другой точ-
/¦——^ ки множества S.
V *J * Отметим, что интуи-
, * # тивно решение этой за-
• * дачи представляется как
• . построение разбиения
плоскости на области, а каждая из которых яв-
ляется локусом точек (х,у), более близких к некоторой точке множества S, чем к любой другой точке S. Заметим также, что если такоё"~~раз-биение плоскости известно, то, применив процедуру поиска, определяющую какой из областей разбиения принадлежит некоторая точка q, можно непосредственно получить решение задачи ПОИСК БЛИЖАЙШЕГО СОСЕДА (задачи Б.5). Исследуем теперь структуру этого разбиения плоскости. Если имеются две точки Pi и pj, то множество точек, более близких к pit чем к р/, есть не что иное, как полуплоскость, определяемая прямой, перпендикулярной отрезку pip; и делящей его пополам, и содержащая точку pi. Обозначим эту полуплоскость #(р,-, pj). Множество точек, более близких к р,-, чем к любой другой точке, которое будем обозначать V(i), получается в результате пересечения N—\ полуплоскостей. Это множество является выпуклой многоугольной областью (см. разд. 1.3.1), имеющей не более JV— 1 сторон. Таким образом,
vd)= П н(Р„р,).
Рис. 5.16. (а)—многоугольник (ячейка) Вороного; (Ь)—диаграмма Вороного.
5.5. Решение задач о близости методом локусов
251
Область V(i) называется многоугольником Вороного, соответствующим точке pi. На рис. 5.16(a) приведен пример многоугольника Вороного [Rogers (1964)]').
Получаемые таким образом N областей образуют разбиение плоскости, представляющее некоторую сеть, называемую диаграммой Вороного. Диаграмму Вороного множества точек S будем обозначать Vor(S). На рис. 5.16(b) приведен пример диаграммы Вороного. Вершины многоугольников определяют вершины диаграммы Вороного, а соединяющие их отрезки — ребра диаграммы Вороного.
