Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Теперь можно обратить внимание на простые многоугольники общего вида, которые будем называть обыкновенными. Существует иерархия свойств, строго упорядоченная отношением «быть подмножеством»:
ВЫПУКЛОСТЬ с ЗВЕЗДНОСТЬ с ОБЫКНОВЕННОСТЬ.
(2.2)
62
Гл. 2. Геометрический поиск
Мы только что видели, что задача о принадлежности звездному многоугольнику асимптотически ничуть не сложнее задачи о принадлежности выпуклому многоугольнику. Но что можно сказать об обыкновенном случае? Один из подходов к этой задаче подсказан тем, что каждый простой многоугольник есть объединение некоторого числа многоугольников специального вида — таких, как звездные или выпуклые, или в конечном итоге треугольников. К сожалению, минимальная мощность k такой декомпозиции может сама оказаться равной O(N) '). Поэтому данный подход сводится к преобразованию простого JV-угольника в Af-вершинный плоский граф. В связи с этим кажется, что задача принадлежности обыкновенному простому многоугольнику не легче, чем, по-видимому, более общая задача о локализации точки в планарном подразбиении, хотя и неизвестно доказательство их эквивалентности. Поэтому мы сосредоточимся на последней из этих задач.
2.2.2. Локализация точки на планарном подразбиении
В главе 1 упоминалось, что планарный граф всегда может быть уложен на плоскости так, что его ребра перейдут в прямолинейные отрезки. Графы, уложенные подобным образом, будут называться плоскими прямолинейными графами (ППЛГ). Любой ППЛГ определяет, вообще говоря, подразбиение плоскости; если в ППЛГ нет вершин со степенью <2, то можно непосредственно убедиться в том, что все ограниченные области этого подразбиения — простые многоугольники. Без потери общности здесь и далее граф предполагается связным.
Чтобы вести поиск в подобной структуре, можно попытаться разбить каждую область на такие многоугольники, для которых поисковая операция относительно проста. Не принимая во внимание на некоторое время сложности получения желаемой декомпозиции — это, безусловно, может оказаться не простым делом, — заметим, что успех в локализации точки зависит от возможности быстро сузить множество компонент декомпозиции, которые следует просмотреть. С другой стороны, скорейшие из известных методов поиска основаны на дихотомии, иначе говоря, на двоичном поиске. Легко убедиться после небольшого размышления, что с точки зрения затрат времени на запрос возможность использовать двоичный поиск важнее, чем минимизация размера исследуемого множества, в связи с логарифмической зависимостью времени запроса от этого размера. Отсюда
') Это очевидно, если компонентами разбиения являются треугольники, поскольку k = N — 3. Но даже для звездных компонент k может достигать величины Г///31 [Chvatal (1975)].
2.2. Задачи локализации точки
63
видно, что потенциально успешный метод локализации точки должен обладать следующими чертами: исходное планарное подразбиение должно преобразовываться в новое, такое, что каждый из составляющих его многоугольников пересекает небольшое и ограниченное число (возможно, ровно одну) исходных областей, и, кроме того, такое, что к нему применим двоичный поиск. Другими словами, главная идея состоит в том, чтобы создать новые геометрические объекты, допускающие двоичный поиск, и в таком виде она была сформулирована Добкином и Липтоном [Dobkin, Lipton (1976)]. Все известные методы, описываемые ниже, по существу, пронизаны этой идеей.
2.2.2.1. Метод полос
Пусть задан ППЛГ G. Проведем горизонтальные прямые через каждую его вершину, как показано на рис. 2.8. Они разделяют плоскость на N + 1 горизонтальных полос. Если провести сортировку этих полос по координате у как часть предобработки, то появится возможность найти ту полосу, в которой лежит пробная точка г. за время О (log TV).
Рис. 2.8. Вершины ППЛГ определяют горизонтальные полосы.
Теперь рассмотрим пересечение одной из полос с графом G. Оно состоит из отрезков ребер графа G. Эти отрезки определяют трапеции1). Поскольку G есть плоская укладка планарного графа, то его ребра пересекаются между собой только в вершинах, а так как каждая вершина лежит на границе полосы, то отрезки ребер внутри полос не пересекаются (рис. 2.9).
Поэтому данные отрезки можно ЦОЛ^сгъю^по^^оштъ_с^^ ва надраво-й-использовать двоичный поиск для определения той трапеции, в которую попала точка г, потратив на это O(logJV) времени. Отсюда получаем оценку времени запроса для худшего случая, равную 0(\ogN).
') Такие трапеции, очевидно, могут вырождаться в треугольники, как показано на рис. 2.9.
64
Гл. 2. Геометрический поиск
Осталось только узнать, сколько ресурсов ушло на предварительную подготовку и запоминание ППЛГ. При наивном подходе кажется, что нужно сортировать все отрезки внутри каждой полосы. Кроме того, поскольку каждая полоса может содер-
/--------------------К
Рис. 2.9. Отрезки ребер графа внутри полосы не пересекаются.
жать О (N) таких отрезков, то кажется, что должны потребоваться затраты: 0(N2\ogN) —для времени и 0(N2) —для памяти. Теперь покажем, как сократить время предобработки до 0(N2). Однако (в данном алгоритме) ничего нельзя сделать для сокращения памяти, поскольку существуют такие ППЛГ, которые требуют квадратичной памяти (рис. 2.10).
