Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Wln(v)= ? W(e); Wout(v)= ? W (е).
eelN(ti) eeOUT(o)
Тогда надо только показать, что веса ребер можно выбрать такими, что:
(1) каждое ребро обладает положительным весом;
(2) для любого vj (j-ф l,N), Win{vj)=Wout(vj).
Условие (1) устанавливает, что каждое ребро принадлежит по крайней мере одной цепи (т.е. свойство 1), а условие (2) гарантирует, что Win(vj) цепей проходят через v,- и их можно выбрать так, чтобы они не пересекались (свойство 2). Реализация условия Ww = Wovt является решением достаточно известной классической потоковой задачи [Even (1979)] и может быть достигнуто за два прохода по графу G. Полагая W(e) = \ для каждого ребра е, в первом проходе — от v\ до vn — мы получим WiN(Vi) г?Г Wour(Vi) для всех некрайних и,-. При втором проходе— от vn до vi — мы получим Wln(vi) ^ WQut(vi), т.е. неко-
им uw
70
Гл. 2. Геометрический поиск
мое выражение. Обозначая vm {v) = | IN (v) | и vout(o) = = |OUT(t>)|, имеем алгоритм
procedure БАЛАНСИРОВКА-ПО-ВЕСУ-В-РЕГУЛЯРНОМ-ППЛГ begin for каждого ребра е do W(e) : = 1 (* инициализация *) for / := 2 until N — 1 do
begin Wm(vt) '•= сумма весов ребер, входящих в vt; dx := крайнее слева ребро, исходящее из ut; mWw(vi)>v0v7(vi)) then W{dx):=Wm{Vi)-
VoUT(Wf) + 1
end (* первый проход*); for i:=N — \ until 2 do
begin Woux{Vi) := сумма весов ребер, исходящих из vt;
d2 := крайнее слева ребро, входящее в vt; \f(Wom(Vi) > Wm(vd) then W (d2) :=
WouAvd - WiN(vt) + W{d2)
end (* второй проход*)
end.
Очевидно, что этот алгоритм требует времени, линейно зависящего от числа ребер и вершин графа G. Данную процедуру можно изменить так, чтобы построение т. е. назначение ребер цепям, проводилось при реализации второго прохода. Для краткости опустим эти детали и покажем на рис. 2.13(a)— (d) конфигурацию веса ребер после инициализации, первого и второго проходов соответственно и чертеж цепей ^ для ППЛГ G с рис. 2.12. Этим заканчивается доказательство того, что регулярный ППЛГ покрывается полным множеством монотонных цепей.
Перед проведением анализа работы этого алгоритма важно показать, как произвольный ППЛГ преобразуется в регулярный. Рассмотрим такую нерегулярную вершину v графа U, которая не имеет, скажем, исходящих ребер (рис. 2.14). Горизонтальная прямая, проходящая через v, протыкает в общем случае пару ребер ех и е2 графа G, ближайших к v слева и справа. (Заметим, что, поскольку v — некрайняя вершина, по меньшей мере один из этих проколов должен существовать.) Пусть ьи — верхняя вершина ребер <?, (;=1,2), и пусть v* — та из вершин {vx,v2}, которая имеет меньшую ординату (например. v2). Тогда отрезок vv* не пересекает ребер G {) и, следовательно, может быть до-
') Это утверждение, вообще говоря, неверно. Контрпример получается, если другая нерегулярная вершина v3, не имеющая входящих ребер, находится внутри треугольника (v, v% и4). Здесь w4 — точка пересечения ребра ег с горизонтальной прямой, проходящей через точку v (см. рис. 2.14). Однако ?то наблюдение не опровергает теорему 2.5, изложенную ниже. Алгоритм регуляризации нуждается при этом в небольшом изменении. — Прим. перев.
бавлен к ППЛГ, тем самым «регуляризуя» вершину v. Данное наблюдение позволяет использовать метод, именуемый вертикальным плоским заметанием (см. разд. 1.2.2). А именно заметаем граф сверху вниз, чтобы регуляризовать вершины, не имеющие исходящих ребер, а затем снизу вверх, чтобы регуляризовать вершины другого типа. В первом случае списком точек
Рис. 2.13. Построение множества <в для Рис. 2.14. Пример типично;'! ППЛГ с рис. 2.12. Метки ребер являются нерегулярной вершины v. их весами после: (а) инициализации; (Ь) первого прохода; (с) второго прохода. Полученное множество цепей изображено на (d).
пересекающихся с этой заметающей прямой, и, кроме того, с каждым интервалом между этими ребрами связана одна вершина (с минимальной ординатой в этом интервале). В процессе заметания для каждой встреченной вершины v реализуем следующие операции: (1) локализуем v (по абсциссе) в одном из интервалов в структуре данных статуса; (2) корректируем эту структуру статуса; (3) если v нерегулярна, добавляем ребро от v до той вершины, которая связана с интервалом, определенным в операции (1). Построение более формального алгоритма мы оставляем для самостоятельного упражнения. Заметим, что регуляризация Л/-вершинного ППЛГ осуществима за время 0(N\ogN) благодаря возможности начальной сортировки ординат его вершин и локализации N вершин в структуре данных
событий является последовательность вершин vn, Vn-u ¦ ¦
v\. Структура статуса заметающей прямой (которая будет реализована деревом, сбалансированным по высоте) задается упорядоченным слева направо списком номеров ребер ППЛГ,
72
Гл. 2. Геометрический поиск
статуса за время О (log Л/) для каждой вершины. Сформулируем этот факт как теорему для будущих ссылок.
Теорема 2.5. N-вершинный ППЛГ можно регуляризовать за время 0(N\ogN) с затратой 0(Л7) памяти.
На рис. 2.15 показан результат регуляризации ППЛГ из рис. 2.8.
