Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
84
Гл. 2. Геометрический поиск
трапеции. При втором проходе выполняется цикл repeat (за исключением строки 10).
Вспомогательная функция БАЛАНС организует из чередующейся цепочки, состоящей из деревьев и ребер, U = T\e{T2e2... ... еп-\Тп — сбалансированное дерево. Каждое дерево Г/ имеет вес W(T,) ^ 0, равный числу вершин ППЛГ, содержащихся в соответствующей трапеции. Вес U равен W (U) = ?/=1 W (Tj). Функция БАЛАНС работает следующим образом:
1. Если W(U)=0 (т. е. U — ехе2 . .. eh-i), то сделать из этих ребер сбалансированное дерево. Иначе:
2.1. Найти такое целое г, чтобы W (Т,)< W (U)/2, a Zr,.iW(T,)^W(U)/2.
2.2. Построить дерево, подобное изображенному на рис. 2.22(a), где U' = Т{е{ . . . Tr_u U" = Tr+ler+l ...Тп, а х' = БАЛАНС [U'), х" = БАЛАНС (U"). (Заметим, что W (W) < W (U)/2 и W (U") < W (U)/2.)
Очевидно, что процедура БАЛАНС требует О (h log h) времени. Действительно, разделение U на (?/', Tr, U") потребует 0(h) времени, а затем последуют два рекурсивных вызова этой же процедуры, применяемых к половинам исходной цепочки.
Рис. 2.22. Пример операции балансирования.
Но еще интереснее анализ высоты сбалансированных деревьев. Заметим для начала, что h — число деревьев в цепочке U, меньшее N, где N, как и ранее, равно числу вершин в ППЛГ. В самом деле, из рис. 2.23 видно, что h — число новых трапеций, на единицу большее числа ребер, накрывающих исходную трапецию. Последнее число ограничено сверху числом ребер, которые можно пересечь одной прямой линией. Теперь заметим, что эти ребра можно считать «диагоналями» простого многоугольника (ограниченного на рис. 2.23 штриховой линией). Если у этого многоугольника s вершин, то в нем не более s — 3 диа-
(Ь)
'2.2. Задачи локализации точм
85
гоналей (потому что эти диагонали определяют триангуляцию данного многоугольника). Поскольку s ^ N (числа вершин ППЛГ), то получаем — 2^N— 2. Теперь можно дока-
зать следующую теорему.
Теорема. Для заданной цепочки U = Т\в\... en-iTh высота 8(U) дерева, построенного с помощью процедуры БАЛАНС, не превосходит 3 log2 W(U) + \\og2N'\ + 3.
Доказательство. Доказательство проведем индукцией по W(U). Начнем с W(U) = 1. В этом случае, процедура БАЛАНС
Накрывающие ребра
Рис. 2.23. Иллюстрация к доказательству того, что h <N (h — число новых трапеций).
дает такое дерево, как на рис. 2.22(a), у которого т/ и г", возможно, пусты, а 77 — дерево, приведенное на рис. 2.22(b). Здесь Т'г и Т" содержат не более чем по N штук О-узлов. Поэтому высота этого дерева не превосходит riog2A/l + 3, и теорема верна. Полагая W(U) = K (целому положительному числу),допустим, что теорема справедлива для всех весов, меньших К. Будем различать два случая:
Случай 1. W{Tr)^K/2. Поскольку верно также, что W(U'), W (?/") ^ К/2, то по предположению индукции 6 (?/'), 6 (?/"), б (7V) < 3 log2 К/2 + riog2 К\ + 3 < 3 log2 К - 3 + riog2 ЛЛ + 3; так что конфигурация на рис. 2.22(a) обеспечивает индуктивный переход.
Случай 2. W(Tr) Ж/2. Поскольку W{U'), W(U") ^ К/2, то доводы для %' и х" будут теми же, что и в случае 1. Относительно 7V заметим, что оно соответствует трапеции. Поэтому под действием процедуры ТРАПЕЦИЯ Т, получает структуру, показанную на рис. 2.22(b), где Т'Г и Г" сами являются сбалансированными деревьями, и в силу медианного разбиения W (7^),
Гл. 2. Геометрический поиск
W (Т") ^ W (Try2 ^ /С/2. Следовательно, для некоторого h" < N имеем 6(Т'Г), 6 (Т") ^ 3 log W (Tr)/2 + |Tog2 h"~\ + 3^3 log К — — 3 + Rogo Л/1 + 3, что и завершает доказательство.
Поскольку для ППЛГ верно, что W(U) ^N, то высота дерева поиска для ППЛГ не превосходит 4Tlog2 А/1-j- 3.
Наконец, рассмотрим цикл repeat в процедуре ТРАПЕЦИЯ. Для каждого просматриваемого ребра (т. е. взятого из списка ?)* эта процедура осуществляет константный объем вычислений в строке бив строках либо 8—10, либо 12—14. Следовательно,
Медиана в R' Трапеция R" Трапеция R
Рис. 2.24. Иллюстрация механизма деления ребра.
общая работа, проделанная в этом цикле, пропорциональна суммарному числу фрагментов ребер, порождаемых данным алгоритмом. Теперь оценим это число сверху. Обращаясь к рис. 2.24, видим, что ребро делится впервые тогда, когда его концы лежат в разных слоях, определяемых медианой трапеции R. После этого деления верхний фрагмент ребра попадает в трапецию R'. Если медиана R' делит е (худший случай), то е накрывает нижний слой в R', а следующее его деление может произойти только в верхнем слое R'. Аналогичные соображения применимы к фрагменту е, попавшему в нижний слой R. Поэтому, выражая число делений верхнего фрагмента ребра е как функцию c(s') от числа s' вершин в R', мы получаем грубую оценку: с («')<; ^ 1 + c(s"), где s" — число вершин в трапеции R", как показано на рис. 2.24. Поскольку s" < s'/2, мы получаем c(s') ^ ^ log2 s', а поскольку s' < N/2, то общее число делений е не превосходит 2 log2 N — 2. Эта оценка доказывает два утверждения. Первое: общая работа, производимая в цикле repeat, пропорциональна 0{N\ogN), поскольку имеется О (А/) ребер, а каждое ребро разделено на не более чем О (log Л/) фраг-
