Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Такая организация неявным образом дает циклическую упорядоченность против часовой стрелки ребер, инцидентных любой вершине диаграммы, а также циклическую упорядоченность по часовой стрелке ребер любой грани.
Теперь, как обычно, рассмотрим сначала вопрос о нижних оценках для времени, необходимого для построения диаграммы Вороного. Ответ на этот вопрос дает следующая простая теорема:
Теорема 5.12. В рамках модели алгебраических деревьев вычислений для построения диаграммы Вороного множества из N точек требуется ?1 (N log N) операций в худшем случае.
Доказательство. Далее мы увидим, что все задачи о близости точек можно свести за линейное время к задаче ДИАГРАММА ВОРОНОГО, и, следовательно, существует много различных способов доказательства этой теоремы. Но здесь мы ограничимся очень простым доказательством. В одномерном случае диаграмму Вороного множества, состоящего из N точек, представляет последовательность из N—1 точек, отделяющих друг от друга последовательные точки исходного множества и расположенных посередине между ними. Имея эту последовательность, можно за линейное время получить упорядоченный список точек исходного множества. Таким образом, задача СОРТИРОВКА может быть сведена за линейное время к задаче ДИАГРАММА ВОРОНОГО.
Простой (и достаточно грубый) подход к построению диаграммы Вороного заключается в поочередном построении многоугольников, входящих в диаграмму. Так как каждый многоугольник Вороного получается в результате пересечения N— 1 полуплоскостей, то, используя метод, который будет рассмотрен в tjl^JLt- можно построить этот многоугольник за время 0(N\ogN), что дает для полного времени построения всех многоугольников оценку 0(;V2logjV). Далее будет показано, что вся диаграмма целиком может быть построена за оптимальное время Q(N\ogN), а это значит, что асимптотически задача построения всей диаграммы является не более сложной, чем задача построения лишь одного из многоугольников этой диаграммы!
9*
260 Гл. 5. Близость: основные алгоритмы
В действительности, несмотря на кажущуюся сложность, задача ДИАГРАММА ВОРОНОГО прекрасно подходит для применения метода «разделяй и властвуй». Успех применяемого нами метода зависит от различных структурных свойств диаграммы, использование которых позволяет произвести объединение решений подзадач за линейное время.
Попытаемся в общих чертах описать алгоритм.
procedure ДИАГРАММА-ВОРОНОГО (предварительный вариант)
Шаг 1. Разделить множество 5 на два приблизительно равных подмножества Si и S2.
Шаг 2. Рекурсивно построить Vor(5i) HVor(S2). Шаг 3. Объединить Vor(Si) и Vor(52) и таким образом получить Vor(S).
Предположим, что шаг 1 алгоритма можно выполнить за время O(N) (позже мы докажем это). Если обозначить через Т (Л/) полное время работы алгоритма, то на выполнение шага 2 потребуется время, равное примерно 2T(N/2). Таким образом, если удастся объединить Vor (Si) и Vor(S2) за линейное время, получив в результате диаграмму Вороного Vor(S) всего исходного множества, то мы получим оптимальный алгоритм с временем работы 0(/VlogA7). Но прежде чем браться за более детальную разработку алгоритма, попытаемся ответить на следующий вопрос: на каком основании можно считать, что Vor(Si) и Vor(S2) как-то связаны с Vor(S)?
Чтобы ответить на этот вопрос, определим геометрическую конструкцию, играющую ключевую роль в рассматриваемом подходе.
Определение 5.2. Пусть для заданного разбиения {5Ь52} множества 5 а(51,52) обозначает множество ребер диаграммы Вороного, общих для пар многоугольников V(i) и V(j) диаграммы Vor (S), где pi eSi и р,- е S2.
Совокупность ребер a(ShS2) обладает следующими свойствами.
Теорема 5.13. Совокупность o(S\,S2) является множеством ребер некоторого подграфа диаграммы Vor (S) и обладает следующими свойствами:
(1) o(5i,S2) состоит из циклов и цепей, не имеющих общих ребер. Если некоторая цепь содержит лишь одно ребро, то это ребро является прямой линией; иначе два крайних ребра цепи являются лучами.
(2) Если множества Si и S2 линейно разделимы1), то
') Если разделяющей прямой принадлежат более одной точки, то всех их следует отнести к одному и тому же множеству разбиения.
5.5. Решение задач о близости методом локусов
261
o(S\,S2) состоит из единственной монотонной цепи (см. разд. 2.2.2.2).
Доказательство. (1) Если представить, что каждый из многоугольников {V(i): pi е= S\} покрашен в красный цвет, а каждый из многоугольников {V(j): р, se S2}—в зеленый цвет, то Vor(S) превратится в двухцветную карту. Хорошо известно, что границы между многоугольниками различных цветов представляют циклы и цепи, не имеющие общих ребер [Bollobas (1979)]. (Заметим, что две' компоненты множества a(SuS2) могут иметь общую вершину лишь в случае, когда степень этой
Рис. 5.24. Множества S, и S2 разделимы вертикальной прямой; (а)—каждая компонента o(Sb S2) является монотонной по вертикали цепью; (Ь) — a(Si,S2) состоит из единственной цепи.
вершины не меньше четырех. Поэтому, если все вершины диаграммы Вороного имеют степень три, то компоненты множества o(S\,S2) не пересекаются также и по вершинам.) Каждая компонента множества a(S],S2) разбивает плоскость на две части. Таким образом, цепь либо содержит единственное ребро, представляющее прямую линию, либо ее первое и последнее ребра являются лучами. Что доказывает свойство (1).
