113
правок
Изменения
м
→Мотивация
==Мотивация==
Существует ли метод локализации со временем поиска за <tex>O(\log n)</tex>, использующий менее чем квадратичную память? Эта задача оставалась не решенной довольно долго. Но все же была решена Липтоном и Тарьяном в 1977-1980 гг. Но их метод оказался на столько настолько громоздким, а оценки времени его эффективности содержат слишком большую константу, что сами авторы не считали этот метод практичным, но его существование заставляет думать, что может найтись практичный алгоритм с временной оценкой <tex>O(\log n)</tex> и линейной памятью.
Недавно Киркпатриком был предложен оптимальный метод, дающий ответ на ожидания Липтона и Тарьяна, {{---}} детализация триангуляции.
которых соответствует какой-нибудь триангуляции. Последовательность триангуляций и соответствующая ей структура $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)$.
