Применение геометрических остовных сетей: различия между версиями

Упомянутое в теореме 3 вычисление за константное время осуществляется посредством сведения задачи к задаче нахождения ответов на запросы о наименьшем общем предке для пар вершин дерева, для которой Бендер и Фарах-Колтон недавно предложили решение с константным временем выполнения [4].

Используя инструменты группировки и усечения, а также алгоритмы Гудмундссона и др. [11], можно доказать следующую теорему.