Изменения

Существует ли метод локализации со временем поиска за <tex>O(\log n)</tex>, использующий менее чем квадратичную память? Эта задача оставалась не решенной довольно долго. Но все же была решена Липтоном и Тарьяном в 1977-1980 гг. Но их метод оказался на столько настолько громоздким, а оценки времени его эффективности содержат слишком большую константу, что сами авторы не считали этот метод практичным, но его существование заставляет думать, что может найтись практичный алгоритм с временной оценкой <tex>O(\log n)</tex> и линейной памятью.

<wikitex>[[Файл:кирк1.png|right|420px|thumb|Триангуляция в охватывающем треугольнике.]]Пусть планарный N-вершинный граф задает триангуляцию нашего многоугольника (если это не так, то воспользуемся методом триангуляции многоугольника за время $O (n \log n)$. Напомним, что триангуляция на множестве вершин $V$ есть планарный граф с не более чем $3 |V| - 6$ ребрами ([[Формула_Эйлера |формула Эйлера]]). Для удобства описания алгоритма поместим нашу триангуляцию в охватывающий треугольник и построим триангуляцию области между нашими объектами. После этого преобразования все триангуляции будут обладать тремя границами и ровно $3 |V| - 6$ ребрами. 

<wikitex>[[Файл:кирк2.png|right|420px|thumb|Последовательность триангуляций.]][[Файл:кирк3.png|right|420px|thumb|Структура триангуляций.]]Итак, имеется N-вершинная триангуляция $G$, и пусть строится последовательность триангуляций $S_1, S_2, \dots, S_{h(N)}$, где $S_1 = G$, а $S_i$ получается из $S_{i - 1}$ по следующим правилам:

Теперь построим структуру данных $T$ для поиска. Эта структура представляет собой направленный ацикличный граф, вершинами которого будут наши треугольники. Определим эту структуру следующим образом: из треугольника $R_k$ будет вести ребро в треугольник $R_$$R_j$, если при построении $S_i$ из $S_{i-1}$ мы имеем

* $R_j \cap R_k \not ne \bigcircvarnothing $ Очевидно, что треугольники из $S_1$ (и только они) не имеют исходящих ребер. Для ясности удобно изобразить $T$ в рассмотренном виде, то есть помещая его узлы в горизонтальные строки, каждая из которых соответствует какой-нибудь триангуляции. Последовательность триангуляций и соответствующая ей структура $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)$. '''Свойство 2'''. Каждый треугольник $R_i \in S_i$ пересекается не более чем с $H$ треугольниками из $S_{i-1}$ и наоборот.Первое свойство немедленно влечет за собой следствие, что $h(N) \le \left \lceil \log_{1/a}N \right \rceil = O(log N)$, поскольку при переходе от $S_{i-1}$ к $S_i$ удаляется по меньшей мере фиксированная доля вершин. Также из этих свойств следует, что память для $T$ равна $O(N)$. Действительно, заметим, что эта память используется для хранения узлов и указателей на их потомков. Из [[Формула_Эйлера|теоремы Эйлера]] о плоских графах следует, что $S_i$ содержит $F_i < 2N_i$ треугольников. Число узлов в $T$, представляющих треугольники из $S_i$, не превосходит $F_i$ (только те треугольники, которые действительно принадлежат $S_i$, появляются на соответствующем «ярусе» $T$). Отсюда следует, что общее число узлов в $T$ меньше, чем$2(N_1 + N_2 + \dots + N_{h(N)}) \le 2N_1(1 + a + a^2 + \dots + a^{h(N) - 1}) < \frac{2N}{1 - a}$.Что касается памяти, используемой под указатели, то по свойству 2 каждый узел имеет не более $H$ указателей, поэтому не более $\frac{2NH}{1-a}$ указателей появится в $T$. Это доказывает последнее утверждение.