Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 25

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 180 >> Следующая


Теперь, после того как мы определили, что метод цепей применим к любому ППЛГ, — возможно, после его регуляризации — проанализируем его эффективность. Верхняя оценка време-

Рис. 2.15. Регуляризованный ППЛГ. в каждой из которых N/2 ре-

лось бы, демонстрирует обескураживающую зависимость 0(N2)\ Однако дела совсем не так плохи, если обратить внимание на то, как в алгоритме используются цепи. Безусловно, цепи используются в схеме двоичного поиска. Алгоритм двоичного поиска на полностью упорядоченном множестве S индуцирует естественную иерархию на S, представленую двоичным деревом с корнем; процесс поиска соответствует проходу в этом дереве от корня к листу. Если естественным образом пронумеровать цепи, скажем, слева направо, то ребро е, принадлежащее более чем одной цепи, будет принадлежать всем элементам множества (интервалу) последовательных цепей. Теперь предположим, что цепи сопоставлены узлам дерева двоичного поиска. Если ребро е принадлежит нескольким цепям какого-то интервала, то существует единственный элемент С* в этом интервале, который является общим предком ') для всех остальных элементов из этого

'') Согласно стандартной терминологии, вершина у,- в корневом дереве Т является предком или предшественником вершины о,, если существует путь от корня Т, содержащий и Vi, и vjt причем vt ближе к корню.

ни поиска для наихудшего случая О (log р- log г) = О (log2 N) уже была установлена. Причем эта оценка достижима, поскольку существует ^-вершинный ППЛГ с О (УлГ) цепями, каждая с 0(-y/N) ребрами (рис. 2.16(a) для Л/ = 16).

Рассмотрим ППЛГ, изображенный на рис. 2.16(b). Этот граф содержит в своем полном множестве N/2 цепей,

Штриховыми линиями изображены ребра, добавленные при заметании сверху вниз, а пунктирными — при заметании снизу вверх.

бер. На первый взгляд этот пример внушает беспокойство, так как в отношении затрат памяти данный метод, каза-

2.2. Задачи локализации точки

73

интервала в дереве поиска. Пусть С — любой из этих остальных элементов; тогда дискриминации точки z относительно С пред-

(a) W

Рис. 2.16 Примеры худших случаев ППЛГ.

(с)

Рис. 2.17. Полное множество монотонных цепей (а), на котором ведется поиск в соответствии с иерархией, выраженной двоичным деревом (Ь). Обходные указатели показаны штриховыми линиями (с).

шествует — в схеме двоичного поиска — дискриминация z относительно С*. Следовательно, ребро е можно отнести только к цепи С*, и на самом деле оно будет отнесено к самой верхней в иерархии цепи из числа тех, которым оно принадлежит. При-

74

Гл. 2. Геометрический поиск

мер такого отнесения иллюстрирует рис. 2.17. Отметим наличие обходных указателей на рис. 2.17(c); однако их число не превосходит числа ребер, отсюда следует, что полную структуру данных для поиска можно разместить в O(N) ячейках памяти.

Что же касается предобработки, то по-прежнему предположим, что ППЛГ задан в виде структуры данных РСДС, описанной в разд. 1.2.3.2. Поскольку кольцо ребер, инцидентных любой вершине v графа G, можно получить за время, линейно связанное с ее степенью, то построение множеств IN (и) и OUT (и) для всех v осуществимо за время O(N).

Процедура балансирования по весу, как мы видели, также проходит за время O(N). Отмечая, что возможный предварительный регуляризующий проход потребует еще O(NlogN) времени, заключаем, что задача предобработки займет 0(N log N) времени. Резюмируем:

Теорема 2.6. Локализацию точки в N-вершинном планарном подразбиении можно реализовать за время О (log2 Л/) с использованием O(N) памяти при затратах 0(N\ogN) времени на предобработку.

В начале разд. 2.2.2.2 было отмечено, что в методе цепей используется новый тип простого многоугольника. Определим эти многоугольники:

Определение 2.4. Простой многоугольник называется монотонным, если его границу можно разбить на две цепи, монотонные относительно одной и той же прямой линии.

Монотонные многоугольники являются весьма интересными геометрическими объектами. Из результатов данного раздела непосредственно следует, что задачу о принадлежности точки монотонному многоугольнику с N вершинами можно решить за время О (log JV); позднее мы увидим, что и триангуляцию монотонного многоугольника, и определение факта монотонности простого многоугольника можно осуществить за оптимальное время 0(N).

2.2.2.3. Оптимальные методы: метод планарного сепаратора и метод детализации триангуляции

Существует ли метод со временем поиска О (log Л/), использующий менее чем квадратичную память? Эта знаменитая задача довольно долго не была решена. Она получила положительное решение благодаря замечательной конструкции, принадлежащей Липтону и Тарьяну [Lipton, Tarjan (1977а, 1977b, 1980)]. Следует обратить внимание на слова «существует ли метод». В действительности этот метод столь громоздок, а оценки

2.2. Задачи локализации точки

75

его эффективности столь откровенно и щедро опираются на «большое О», что Липтон и Тарьян сами высказали следующее предостережение [Lipton, Tarjan (1977b)]: «Мы не считаем этот алгоритм практичным, но его существование заставляет думать, что может найтись практичный алгоритм с временной оценкой О (log Л/) и с оценкой памяти 0(N)». Описание их удивительно искусного метода выходит за рамки данной книги. Вместо этого рассмотрим два недавно предложенных оптимальных метода, дающих ответы на ожидания Липтона и Тарьяна. Первый метод— детализация триангуляции Киркпатрика [Kjrkpatrick
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed