Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
(2) Не теряя общности, предположим, что множества S[ и S2 разделены вертикальной прямой ш, и пусть С—-компонента множества a(Si,S2). Будем двигаться по С, начав движение из некоторой точки q ребра компоненты С в направлении уменьшения «/-координаты до тех пор, пока не достигнем вершины диаграммы уь в которой С поворачивает вверх (рис. 5.24(a)). Ребро У[У2 перпендикулярно отрезку рхр2 и делит его пополам, а ребро V\v3 перпендикулярно отрезку р\р3 и также делит его пополам. Так как y(v3) > y{vx) и y(v2) > y(vx), то х(р3)^ ^ x(Pi) ^ х(р2). Однако, учитывая форму С, точки р2 и рз принадлежат одному и тому же множеству (либо Si, либо S2).
Рз
262 Гл. 5. Близость: основные алгоритмы
Возникающая ситуация противоречит предположению о разделимости Si и S2 вертикальной прямой. Значит, вершина, подобная Vi, не может существовать, а С является монотонной относительно вертикальной прямой. Отсюда следует, что компонента С является цепью.
Предположим теперь, что a(SbS2) содержит по крайней мере две монотонные относительно вертикальной прямой цепи Ci и С2. Произвольная горизонтальная прямая / пересекает каждую из цепей Ci и С2 в единственной точке (в силу монотонности С] и С2). Предположим, что точка пересечения прямой / с С] находится левее точки пересечения I с С2 (рис. 5.24(b)). Тогда в S существуют три точки ри р2 и рз такие, что x(pi)< х(р2) < х{р3). При этом pi и р3 принадлежат одному и тому же множеству разбиения {Si,S2}, что противоречит предположению о разделимости этих двух множеств вертикальной прямой. Поэтому o(Si,S2) содержит лишь одну компоненту, являющуюся монотонной цепью.
В том случае, когда множества Si и S2 являются линейно разделимыми, единственную цепь, содержащуюся в o(Si,S2), будем обозначать а. Если отделяющая прямая m является вертикальной, то можно недвусмысленно говорить о том, что о разбивает плоскость на левую пь и правую nR части. Имеет место следующее важное свойство.
Теорема 5.14. Если множества Si и S2 линейно разделимы вертикальной прямой и при этом Si находится слева от S2, то диаграмма Вороного Vor (5) представляет собой объединение Vor (Si) Л Я? и Vor(S2)fljV).
Доказательство. Все точки множества S, расположенные справа от а, принадлежат S2. Кроме того, все ребра диаграммы Vor(S), расположенные справа от о, разделяют многоугольники V(i) и V(j), где обе точки р; и р,- принадлежат S2. Отсюда следует, что каждое ребро диаграммы Vor(S), попадающее в ля, либо совпадает с некоторым ребром Vor(S2), либо является его частью. Аналогичные утверждения справедливы
И ДЛЯ Jtz..
Предыдущая теорема дает ответ на вопрос о том, какая связь имеется между Vor (Si), Vor(S2) и Vor(S). А именно если множества Si и S2 линейно разделимы (а это полностью в нашей власти и может быть реализовано на шаге 1 алгоритма), то теорема дает метод, позволяющий выполнить объединение Vor (Si) и Vor(S2). Пересмотренный вариант алгоритма приведен ниже.
[) Диаграмма Вороного Vor(S) представляет собой объединение Vor(S,) П ял, Vor(S2) П пЛ и а. — Прим. перев.
5.5. Решение задач о близости методом локусов
263
procedure ДИАГРАММА-ВОРОНОГО Шаг 1. Разделить множество S на два приблизительно равных подмножества Si и S2, использовав для этого медиану по х-ко-ординате.
Шаг 2. Рекурсивно построить Vor(Si) и Vor(S2). Шаг 3'. Построить ломаную а, разделяющую Si и S2. Шаг 3". Удалить все ребра диаграммы Vor(S2), расположенные слева от а, и все ребра Vor(Si), расположенные справа от о. В результате получаем Vor(S) — диаграмму Вороного для множества в целом.
(а)
V
(Ь)
Рис. 5.25. Диаграмма Вороного левого (а) и правого (Ь) множеств.
Очевидно, что успешное выполнение этой процедуры зависит от того, насколько быстро мы сможем построить о, так как шаг 3" не вызывает затруднений. Для наглядности на рис. 5.25(a) и 5.25(b) отдельно показаны Vor(Si) и Vor(S2) соответственно, а на рис. 5.26 они представлены вместе с а.
Если говорить о времени обработки, то начальное разбиение множества S с использованием медианы по х-координате
Гл. 5. Близость: основные алгоритмы
может быть выполнено за время O(N) с помощью стандартного алгоритма поиска медианы. Кроме того, шаг 3" может быть выполнен за время 0(|Si| + |S2|) = O(N). Остается лишь найти эффективный способ построения разделяющей цепи а.
Рис. 5.26. Наложение Vor(S,), Vor(S2) и ст.
Рассмотрим теперь решение этой задачи [Shamos, Ноеу (1975), Lee (1978), (1980а)].
5.5.2.1. Построение разделяющей цепи
Первый шаг в построении разделяющей цепи о заключается в определении двух ее лучей. Заметим, что каждый луч цепи о перпендикулярен опорному отрезку (каждый своему) к CH(Si) и CH(S2) и делит его пополам. Отметим также, что так как по предположению Si и S2 линейно разделимы, то имеются в точности два опорных отрезка к CH(Si) и CH(S2) (тем самым подтверждается, что o(Si,S2) состоит лишь из одной цепи о). Если теперь (по индукции) предположить, что уже построены эти две выпуклые оболочки, то два опорных отрезка, которые мы обозначим h и t2, строятся (самое большее) за линейное время (см. разд. 3.3.5) после чего легко определяются лучи цепи а (рис. 5.27). Заметим, что в качестве побочного результата мы получаем также CH(S), обеспечивая тем самым наличие выпуклых оболочек, необходимых для шага индукции.
