Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
(3) Иначе, когда и смежна как с vu так и с и,-, добавить диагонали uv2, uv3, ..., uvi-i. (В этом случае обработка заканчивается (рис. 6.9(c)).)
Корректность алгоритма зависит от того, лежат ли добавляемые диагонали целиком внутри многоугольника. Рассмотрим, например, диагональ (uv2), добавляемую в случае (1). Ни одна из вершин v3, ..., vi не может находиться внутри или на границе треугольника (u,v\,v2), так как внутренние углы в вершинах v2, v3, ..., vi~\ равны не менее чем 180° и это приводит к тому, что и и v3, ..., vi находятся по разные стороны от прямой, содержащей отрезок v\v2. Никакая другая вершина многоугольника не может находиться внутри или на границе этого треугольника, так как все такие вершины имеют у-координату, меньшую чем вершина и. Ни одна точка внутри треугольника не может быть внешней для многоугольника, так как в этом случае ломаная прошла бы через внутренность треугольника и по крайней мере одна из его вершин оказалась внутри треугольника. Таким образом, диагональ uv2 целиком лежит внутри многоугольника. Доказательства для случаев (2) и (3) проводятся аналогично, и, кроме того, довольно просто можно проверить, что свойства стека являются инвариантом алгоритма.
Проанализируем работу алгоритма. Слияние цепей, производимое вначале, может быть выполнено за время O(N). В процессе триангуляции каждая вершина заносится в стек и просматривается в точности один раз, за исключением, когда в случае (2) не выполняется условие «пока i > 1 и угол (uvtVi-i) < 180°». Если отнести соответствующую работу, так же как и затраты, связанные с доступом к верхнему и нижнему элементам стека, на счет обработки текущей вершины и, то очевидно, что эта процедура может быть выполнена также за время O(N). В результате получаем следующую теорему:
Теорема 6.5. Триангуляция монотонного многоугольника с N сторонами может быть выполнена за время O(N), что является оптимальным.
6.3. Обобщения диаграммы
Объединяя этот результат с полученным ранее, согласно которому прямоугольник rect(S) можно разбить на монотонные многоугольники за время O(NlogN), и припомнив нижнюю оценку для задачи триангуляции, получаем следующую теорему:
Теорема 6.6. Триангуляцию с ограничением на множестве из N точек можно выполнить за время Q(N\ogN), что является оптимальным.
Отметим, однако, что теорема 6.6 не применима в случае триангуляции простого многоугольника, так как в этом случае исходно заданные ребра триангуляции уже не являются произвольными. Мы еще вернемся к этому вопросу в разд. 6.5.
6.3. Обобщения диаграммы Вороного
Напомним определение диаграммы Вороного, данное в предыдущей главе: Диаграмма Вороного конечного множества S точек на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу этого множества. В этом определении курсивом выделены три элемента (множество точек, плоскость, один элемент), которые могут служить основой для обобщения. И такие обобщения были сделаны, правда, с различным успехом в каждом из этих трех направлений.
Прежде всего, оставаясь, как и прежде, в плоскости (т. е. в двумерном пространстве), можно расширить заданное множество, добавив помимо точек другие геометрические объекты, такие как отрезки, окружности и т. п. Однако в этой книге это направление подробно рассматриваться не будет (см. разд. 6.5).
Далее в поисках структуры данных, обеспечивающей эффективное решение задачи поиска й-ближайших соседей (см. задачу Б.6 в разд. 5.1), может возникнуть желание определить области, содержащие точки, более близкие к некоторому заданному подмножеству из k элементов множества S, чем к любому другому подмножеству с таким же числом элементов. Любопытно, что если положить k равным N — 1, то получится диаграмма Вороного дальней точки.
И наконец, хотя определение обычной диаграммы Вороного на случай пространства произвольной размерности очевидно, ее построение связано со значительными алгоритмическими проблемами. Действительно, можно легко показать, что при заданном числе точек N количество элементов, необходимых для описания диаграммы Вороного, растет экспоненциально в за-
296
Гл. 6. Близость: варианты и обобщения
висимости от размерности пространства. Это — явление, с которым мы уже сталкивались, решая задачу о выпуклой оболочке. Впрочем, связь между диаграммами Вороного и выпуклыми оболочками далеко не исчерпывается фактом экспоненциального роста соответствующих им описаний.
6.3.1. Диаграмма Вороного высших порядков на плоскости
Диаграмма Вороного, являясь очень мощным средством, не дает ничего, когда речь идет о наиболее удаленных точках, k ближайших точках и других метрических отношениях.
Рис. 6.10. Диаграмма Вороного второго порядка. Точки помечены своими номерами. Некоторые многоугольники Вороного в диаграмме второго порядка могут быть пустыми. Например, отсутствует многоугольник (5,7).
Как таковая, диаграмма Вороного не может быть применена для решения поставленных задач. Затруднение вызвано тем, что мы рассматривали многоугольник Вороного, связанный с одной точкой. Но такое ограничение вовсе не является необходимым, и будет полезно поговорить об обобщенном многоугольнике Вороного V(T) подмножества точек Т [Shamos, Ноеу (1975)], определяемом так:
