Изменения

Перейти к: навигация, поиск

Диаграмма Вороного

1 байт добавлено, 03:15, 1 февраля 2014
м
Случай сильно пересекающихся сайтов
Если же мы хотим вставить в диаграмму отрезок <tex>t</tex>, то вставляем сначала его крайние точки <tex>p'_t</tex> и <tex>p''_t</tex>. Затем, начиная с <tex>p'_t</tex>, ищем первый конфликт <tex>t^\circ</tex> с текущей диаграммой Вороного и ищем всю область конфликтов. Во время этого поиска, прежде чем тестировать ребро Вороного <tex>e</tex> существующей диаграммы на потенциальный конфликт, мы проверяем, не пересекается ли <tex>t^\circ</tex> с одним из сайтов, связанных с <tex>e</tex>. Если такой сайт <tex>S_i</tex> найден, то поиск останавливается. Если <tex>S_i</tex> {{---}} точка, <tex>p_i</tex>, то вставляем отрезки <tex>p'_tp_i</tex> и <tex>p_ip''_t</tex> рекурсивно. Если <tex>S_i</tex> {{---}} отрезок <tex>t^\circ_i</tex>, то сначала проверяем, не принадлежит ли один из <tex>t^\circ</tex>, <tex>t^\circ_i</tex> другому. Если так и есть, то прекращаем работу, иначе вычисляем точку пересечения <tex>p_+</tex> отрезков <tex>t^\circ</tex> и <tex>t^\circ_i</tex>, вставляем её в диаграмму, а затем рекурсивно вставляем отрезки <tex>p'_tp_+</tex> и <tex>p_+p''_t</tex>.
Время работы данного алгоритма составляет <tex>O((n + m)\log^2m)</tex>, где <tex>n</tex> {{---}} количество элементов во входном множестве <tex>\Sigma_I</tex>, а <tex>m</tex> {{---}} количество пар сильно пересекающихся сайтов.
==Ссылки==
64
правки

Навигация