Алгоритм Киркпатрика детализации триангуляции

Мотивация

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

Недавно Киркпатриком был предложен оптимальный метод, дающий ответ на ожидания Липтона и Тарьяна, — детализация триангуляции.