113
правок
Изменения
м
→Мотивация
==Мотивация==
Существует ли метод локализации со временем поиска за <tex>O(\log n)</tex>, использующий менее чем квадратичную память? Эта задача оставалась не решенной довольно долго. Но все же была решена Липтоном и Тарьяном в 1977-1980 гг. Но их метод оказался на столько настолько громоздким, а оценки времени его эффективности содержат слишком большую константу, что сами авторы не считали этот метод практичным, но его существование заставляет думать, что может найтись практичный алгоритм с временной оценкой <tex>O(\log n)</tex> и линейной памятью.
Недавно Киркпатриком был предложен оптимальный метод, дающий ответ на ожидания Липтона и Тарьяна, {{---}} детализация триангуляции.
==Описание алгоритма==
===Предобработка===
<wikitex>[[Файл:кирк1.png|right|350px420px|thumb|Триангуляция в охватывающем треугольнике.]]Пусть планарный N-вершинный граф задает триангуляцию нашего многоугольника (если это не так, то воспользуемся методом триангуляции многоугольника за время $O (n \log n)$. Напомним, что триангуляция на множестве вершин $V$ есть планарный граф с не более чем $3 |V| - 6$ ребрами ([[Формула_Эйлера |формула Эйлера]]). Для удобства описания алгоритма поместим нашу триангуляцию в охватывающий треугольник и построим триангуляцию области между нашими объектами. После этого преобразования все триангуляции будут обладать тремя границами и ровно $3 |V| - 6$ ребрами.
</wikitex>
===Структура данных===
которых соответствует какой-нибудь триангуляции. Последовательность триангуляций и соответствующая ей структура $T$ показаны на рисунке. Треугольники пронумерованы в порядке их появления. Кружком обведены вершины, которые удалены на данном шаге. </wikitex>
====Выбор множества удаляемых вершин====
<wikitex>Как уже упоминалось, от выбора множества вершит вершин триангуляции, которые будут удалены при построении $S_i$ по $S_{i-1}$ существенно зависит эффективность метода. Предположим, что можно выбрать это множество так, чтобы выполнялись следующие ''свойства'' ($N_i$ обозначает число вершин в $S_i$):
'''Свойство 1'''. $N_i = a_i N_{i-1}$, где $a_i \le a < 1$ для $i = 2,\dots , h(N)$.
'''1. ''' Для проверки первого свойства воспользуемся некоторыми особенностями плоских графов. Из [[Формула_Эйлера | формулы Эйлера]] для плоских графов, в частном случае триангуляции, ограниченной тремя ребрами, следует, что число вершин $N$ и число ребер $e$ связаны соотношением
$e = 3N - 6$.
Пока в триангнуляции есть внутренние вершины (в противном случае задача тривиальна), степень каждой из трех граничных вершин не меньше трех. Поскольку существует $3N - 6$ ребер, а каждое ребро инцидентно двум вершинам, то сумма степеней всех вершин меньше $6N$. Отсюда сразу следует, что не менее $ \frac{N}{2}$ вершин имеет степень меньше 12. Следовательно, пусть $K = 12$. Пусть также $v$ {{---}} число выбранных вершин. Поскольку каждой из них инцидентно не более $K-1 = 11$ ребер, а три граничные вершины не выбираются, то мы имеем
$v \ge \left \lfloor \frac{1}{12}(\frac{N}{2} - 3) \right \rfloor $.
Следовательно, $a \cong 1 - \frac{1}{24} < 0,959 < 1$, что доказывает справедливость свойства 1.
==Источники==
* Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. {{---}} М.: Мир, 1989. {{---}} 478 с. {{---}} ISBN 5-03-001041-6
[[Категория: Вычислительная геометрия]]
