Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Рассмотрим теперь многоугольник V(T) диаграммы Vork(S), где Т = {pi, рк}. Известно, что V(T) является
выпуклым многоугольником. Пусть v — одна из его вершин. Вершина v является общей для трех многоугольников диаграммы Vork(S): V(T), V(Ti) и V(T2). Различают два случая1):
(D\T®Tl@T2\ = k + 2 (кфЫ-\), (2) \T®Tl®T2\ = k-2 (кф1).
В случае (1) вершина и называется вершиной ближнего типа, а в случае (2)—вершиной дальнего типа. Чтобы извлечь некоторую пользу из введенной классификации, отметим, например, что в случае (1) имеем
(а) 7- = /?,иЫ, 7\ = Я, U {/>*+,}, 7,2 = /?1U{p*+2}, где Д, =
= {pi, рк-\). Так что, если удалить R\ из 5, то вершина v
') Символ Ф обозначает симметрическую разность множеств
306
Гл. 6. Близость: варианты и обобщения
и инцидентные ей ребра (которые превратились теперь в бесконечные лучи) образуют диаграмму Вороного ближней точки множества {pk, Pk+i, р*+г}- В противоположность этому в случае (2) обычно имеет место
(b) Т = R2{] {Pk-u P„h 7i = *2U{P*-«. Pk+ih T2 = R2U{pk, pk+i),
где R2={pu Pk-2}- Если снова удалить R2 из 5, то вершина v и инцидентные ей ребра образуют диаграмму Вороного дальней точки множества {pk-i, pk, Рш}1)- Интересен следующий факт: окружность Делоне с центром в точке v содержит внутри k—1 точек множества S, если v вершина ближнего типа, и k — 2 точек в противном случае.
Кроме того, предположим, что о —вершина ближнего типа диаграммы Vor*(S). Пусть v является общей вершиной многоугольников V(T), V(Ti) и V{T2), как и в случае (а) выше. Если в некоторой подходящей окрестности вершины v заменить каждое из трех инцидентных ей ребер на его продолжение за вершину v, то вершина v станет общей вершиной трех новых многоугольников, которыми, как нетрудно видеть, будут V(T\}Ti), V(T\jT2) и У(Г, U Г2). Но | Т U Тх \ = | Т{] Т2\ = = | Т\ (J Гг | = k + 1. Таким образом, в результате замены ребер, инцидентных вершине ближнего типа, на их продолжение в диаграмме VoTk(S), эта вершина становится вершиной дальнего типа диаграммы Vorft+I(5)! Короче говоря, в этом заключается основная идея для метода построения последовательности диаграмм Vor2(5), Vor3(S), ..., Vor^-i (S).
Продолжая анализ механизма алгоритма построения диаграммы Вороного, предположим, что вершина ближнего типа v диаграммы Vorfe(5) смежна с некоторой вершиной дальнего типа i>i (рис. 6.16). Это значит, что вершина v была порождена в Vork(S) в результате описанной выше операции продолжения ребер, инцидентных вершинам ближнего типа диаграммы Vor^_i(S) (одной из таких вершин является вершина vi). В свою очередь при построении Vorft+i(5) будут продолжаться ребра, инцидентные вершине v. При этом в ходе этого процесса будет удалено ребро v\v и, таким образом, вершина v\ исчезает из диаграммы Vor*+1(S). Образно говоря, это обсуждение иллюстрирует жизненный цикл вершины диаграммы Вороного: вершина появляется в двух диаграммах Вороного, имеющих последовательные порядки, при этом сначала это вершина ближнего типа, а затем дальнего типа.
') Заметим, что VoiV(S) содержит лишь вершины ближнего типа, а Vorv_i(S) — лишь вершины дальнего типа.
6.3. Обобщения диаграммы
Построение диаграммы Work+\(S), по существу, сводится к разбиению каждого многоугольника диаграммы Vork(S) на части многоугольников диаграммы Vorft+i(S). Это эквивалентно определению пересечения каждого многоугольника V(T) диаграммы Vorfe(S) с обычной диаграммой Вороного Vori(S — Т). Однако для этого вовсе не обязательно вычислять Vori(5 — Т) полностью, а достаточно найти лишь ту ее часть, которая является внутренней для V(T). В частности, пусть е—ребро многоугольника V(T), инцидентное некоторой вершине ближнего типа v. Тогда е принадлежит границе двух многоугольников V(T) и V(T'), где \Т®Т'\ = 2, и находится внутри V(T[)T'),
Рис. 6.16. Иллюстрация «жизненного цикла» вершины диаграммы Вороного.
являющегося многоугольником диаграммы Vorft+i(5). Отсюда следует, что если число вершин ближнего типа на границе многоугольника V(T) равно s, то V(T) будет разбит на s частей, если он ограничен, и на (s + 1) частей, если он неограничен. Так как вершины ближнего типа определяют подмножество множества 5 — Т, влияющее на разбиение многоугольника V(T), то последнее можно получить либо путем построения за время О (slogs) обычной диаграммы Вороного, либо воспользовавшись специальным методом, разработанным Ли [Lee, (1976, 1982)], который также требует время О (slogs). В любом случае, если число вершин ближнего типа в диаграмме Vorft(S) равно то диаграмма Vorfe+1(S) может быть получена за время, не превосходящее О (Va) log V<,n).
Ли [Lee (1982)] провел подробный анализ различных параметров диаграммы Yovk(S). В частности, приведем без доказательства следующую лемму:
Лемма 6.5. Число вершин ближнего типа диаграммы
VoTk(S) ограничено сверху величиной
Л-
второго типа в VorK (S) первого типа в VorH.j (S)
2k(N—l)-k{k-l)-t. v,
Гл. 6. Близость: варианты и обобщения
где v.- — число неограниченных областей в диаграмме Vork(S).
