Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
_ гим деревом леса) они
указали однородное правило выбора, перед использованием которого в очередь помещаются все деревья, содержащие по одной вершине.
1. Выбрать дерево из начала очереди.
2. Если дерево Т" получено в результате объединения дерева Т с некоторым другим деревом Т', то удалить Г и Г' из очереди и добавить Т" в конец очереди.
Так как каждый раз производится объединение двух деревьев и исходно в очереди имеются N деревьев, то основной шаг алгоритма выполняется в точности (N— 1) раз.
Определим для каждого дерева Т, находящегося в очереди, целое число, называемое этапом и вычисляемое следующим образом: этап(Т)=0, если |Г|=1, и этап(Т) = тт(этап{Т'), этап(Т"))-{- 1, если Т является результатом объединения деревьев Т и Т". Очередь деревьев обладает интересным свойством: в любой момент работы алгоритма совокупность чисел этап(Т) в порядке от начала к концу очереди образует неубывающую последовательность. Будем говорить, что этап j завершен, если из очереди удалено дерево Т, для которого этап(Т) = /, и ни для одного другого дерева Т' в очереди значение этап(Т') не равно /'. Заметим, что после завершения этапа j очередь содержит не более N/2'+1 элементов, а всего
Рис. 6.1. Иллюстрация условия 1/еД(р).
доказательству
6.1. Евклидовы минимальные остовные деревья
279
имеется не более Rog2./V"] этапов1). Последующая обработка происходит следующим образом. Выбрав из очереди первый элемент Т (при этом этап(Т)= j), среди ребер, соединяющих вершины дерева Т с вершинами вне его, ищем ребро наименьшей длины. При такой организации обработки на каждом этапе каждое ребро просматривается не более двух раз (за исключением ребер, уже вошедших в некоторое дерево Т). Таким образом, каждый этап обработки может быть выполнен за время, пропорциональное числу ребер, которое в силу планарности графа равно O(N). А так как число этапов не превосходит riog2yVl, то для времени работы алгоритма получаем оценку 0(N\ogN). В этом месте читатель может заметить, что мы могли бы удовлетвориться полученным результатом, так как время, затрачиваемое на построение триангуляции Делоне, равно O(NlogN), и во всяком случае мы имеем оптимальный алгоритм. Однако интересно найти метод, позволяющий получить ЕМОД из диаграммы Вороного за линейное время. Этого можно достичь с помощью операции «очистки», предложенной Черитоном и Тарьяном.
Применение операции очистки имеет целью сжать исходный граф G (в нашем случае это граф триангуляции Делоне), преобразовав его в некоторый граф G*, который в любой момент работы алгоритма содержит лишь необходимую информацию. Это значит, что каждое дерево Т, входящее в лес F, сжимается в единственную вершину графа G (т. е. удаляются все неотобранные ребра, соединяющие вершины дерева Т (хорды)) и, кроме того, удаляются все ребра, за исключением самого короткого из неотобранных, соединяющие деревья Т' и Т". Важно отметить, что если G — планарный граф, то G* тоже будет планарным.
Очистка графа производится сразу же после завершения этапа (см. выше). Не составляет труда предложить такую реализацию, при которой время обработки пропорционально числу ребер графа, удаляемых при очистке.
В заключение приведем формальное описание процедуры построения ЕМОД. Предполагается, что с каждым деревом Т связан список неотобранных ребер, инцидентных вершинам дерева Т.
procedure ЕМОД
1. begin F :— 0;
2. for i := 1 to N do
3. begin этап(р;) := 0;
F^Pt
') To есть этап(Т) может принимать не более n°g2 #1 различных значений. — Прим. перев.
280
Гл. 6. Близость: варианты и обобщения
end; (* очередь инициализирована *)
4. /':=1; (* номеру этапа присваивается следующее значение *)
5. while (F содержит более одного элемента) do
6. begin T<=F;
7. if (этап(Т') = j) then begin очистить граф;
8. i:=i + l end;
9. («, v) := кратчайшее из неотобранных ребер, инцидентных Т (и принадлежит Г);
10. 7":= дерево в F, содержащее v;
11. Т" := объединить^, Т')\
12. удалить 7" из F;
13. этап(Г') := гшп(этап(7/), этап(Г')) + 1;
14. F<=T"(*T" добавляется в конец очереди*) end
end.
Теперь у нас есть все необходимое для анализа алгоритма. По завершении этапа (/—1) в очереди имеется не более N/2' деревьев, и, следовательно, соответствующий граф G* имеет не более N/2' вершин и менее 3N/2J-1 ребер, так как он является планарным. Этап / завершается за время, пропорциональное числу ребер (каждое ребро просматривается на этапе не более двух раз (строка 9)), и то же самое справедливо для времени, затрачиваемого на очистку графа, которая производится по завершении этапа / (строки 7, 8 выполняются непосредственно перед переходом к этапу (/+ 1)). Таким образом, однократное выполнение тела цикла (строки 6—14) происходит за время 0(N/2i). И если вспомнить, что число этапов не превосходит riog2An, получаем следующую верхнюю оценку для полного времени выполнения цикла 6—14:
Г?\^<2ад
где Ki — некоторая константа. Тем самым доказана следующая теорема.
Теорема 6.1. ЕМОД множества S из N точек на плоскости может быть построено, исходя из триангуляции Делоне множества S, за оптимальное время 9 (N).
