Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
ч^\316 Гл. 6. Близость: варианты и обобщения
J> Альтернативный подход, дающий ту же самую оценку сложности, обсуждается в работе [Preparata (1977)J.
охватывает множество, то она и является искомой. Иначе центр с окружности С совпадает с одной из вершин диаграммы >. Vorjv_i(S). Эта диаграмма содержит лишь О (N) точек, а радиусы окружностей, связанных с каждой из ее вершин, равны расстоянию от этой вершины до любой из трех точек, многоугольники которых пересекаются в вершине. М^нш^"™8--""-всем вершинам ряггтпянио дярт рядиуг пкружипгти С_ Ясно, что эту процедуру мбжйо"выполнить за время 0{N log , так как и для определения диаметра множества S, и для построения диаграммы Vorw_i(5) требуется время О(N log N). Кроме того, дополнительно требуется время O(N) для просмотра вершин диаграммы Vor^-i (S)').
В теореме 6.14 резюмируется вышесказанное:
Теорема 6.14. Наименьшую охватывающую окружность множества из N точек можно определить за время O(NlogN).
Оптимален ли этот результат? Для определения минимальной охватывающей окружности в действительности совсем не требуется полной информации о диаграмме Вороного дальней точки. Достаточно иметь лишь ту ее часть, которая попадает в некоторую окрестность центра окружности. Именно эта идея-— позволила Меджиддо разработать оптимальный алгоритм с оценкой Q(N) [Megiddo (1983)]. Основываясь на исходной формулировке (6.5), Меджиддо рассматривал ее как задачу выпуклого программирования. Этот новый изящный метод будет описан в разд. 7.2.5.
Обратимся теперь к задаче, двойственной к только что рассмотренной, т. е. к задаче о наибольшей пустой окружности. Мы покажем, что на плоскости и в пространствах более высокой размерности эта задача может быть решена с помощью диаграммы Вороного. Для простоты и большей конкретности изложения мы будем рассматривать в основном двумерный случай, хотя обобщение на многомерный случай не составляет труда. Имеет место следующая теорема:
Теорема 6.15. Наибольшая пустая окружность для множества из N точек на плоскости может быть построена за время 0(N\ogN).
Доказательство. Пусть на плоскости задано множество S из N точек. Рассмотрим функцию f(x,y), значение которой равно расстоянию между точкой р = (х, у) и ближайшей к ней точкой множества S. Так как условием задачи положение центра наибольшей пустой окружности ограничено выпуклой оболочкой
6.4. Промежутки и покрытия 317
множества S, то мы будем рассматривать пересечение диаграммы Vor(S) с выпуклой оболочкой conv(S). Это пересечение представляет совокупность выпуклых многоугольников, каждый из которых получается в результате пересечения многоугольника диаграммы Вороного с conv(S). Внутри многоугольника диаграммы функция f{x,y) является выпуклой вниз как по х, так и по у, и это справедливо для каждого многоугольника рассматриваемого разбиения выпуклой оболочки. Таким образом, f(x,y) достигает своего максимума в некоторой вершине одного из таких многоугольников1). Эта вершина является либо вершиной диаграммы Вороного (и в этом случае наибольшая пустая окружность является окружностью Делоне), либо точкой пересечения ребра диаграммы Вороного с ребром выпуклой оболочки. Все вершины диаграммы Вороного можно найти за время 0(N\ogN), и, следовательно, остается лишь показать, что можно достаточно быстро найти пересечение выпуклой оболочки и диаграммы Вороного Vor(S)2). Но сначала обратим внимание на следующие два факта.
Свойство 1. Ребро диаграммы Вороного пересекает не более двух ребер оболочки CH(S). Действительно, учитывая выпуклость conv(S), пересечение любой прямой с conv(S) состоит из единственного отрезка (возможно, пустого).
Свойство 2. Каждое ребро оболочки CH(S) пересекает по крайней мере одно ребро диаграммы Вороного. Действительно, каждое ребро оболочки CH(S) соединяет две различные точки множества S, принадлежащие двум различным многоугольникам Вороного.
«Закроем» условно каждый неограниченный многоугольник Вороного отрезком на бесконечно удаленной прямой, лежащей в плоскости (рис. 6.21).
Пусть еи е2, еп — последовательность ребер выпуклой оболочки CH(S), перечисленных в порядке обхода против часовой стрелки, а и — точка пересечения произвольно выбранного ребра в/ с ребром г диаграммы Вороного (согласно свойству 2, точка и всегда существует). Считая, что ребро г ориентировано в направлении из и во внешнюю для conv(S) область, обозначим через V(i) многоугольник диаграммы, расположенный слева от г. Если двигаться из точки и по границе многоугольника V(i) (вне выпуклой оболочки conv(S)), обходя ее против часовой стрелки, то вновь попадем в некоторую точку w пересечения ребра CH(S) с ребром диаграммы. Учитывая вы-
') Имеется в виду максимум на множестве conv(5). — Прим. перев. ) Речь идет о пересечении ребер выпуклой оболочки с ребрами диаграммы Вороного. - Прим. перев.
318
Гл. 6. Близость: варианты и обобщения
пуклость многоугольника V(l) и свойство 2, точка да принадлежит либо ребру е,-, либо ребру e,-+i. Таким образом, каждое ребро многоугольника V(i) проверяется на пересечение с двумя ребрами оболочки CH(S), что делается за постоянное время. После того как найдена точка да, процедура обхода повторяется вновь, только теперь вместо точки и он начинается из да, и так до тех пор, пока вновь не будет достигнута точка и. Дей-
