Быстрая минимальная триангуляция: различия между версиями

Несмотря на то, что все подзадачи на одном и том же уровне могут решаться независимо, у них могут быть общие вершины и дуги, но не антидуги (т.е. пары вершин, не являющиеся смежными). Поскольку процесс триангуляции включает в себя добавление дуг, число антидуг на каждом уровне снижается, и сумма числа антидуг для всех подзадач на одном и том же уровне не может превышать <math>n^2 \; </math>. Алгоритм разбиения на рис. 2 использует этот факт; он имеет время исполнения <math>O(n^2 - m) \; </math>, что в сумме для каждого уровня дает <math>O(n^2) \; </math>. Таким образом, каждый уровень алгоритма быстрой минимальной триангуляции, приведенного на рис. 1, может быть выполнен за время <math>O(n^2 + n^{ \alpha }) \; </math>, где <math>O(n^{ \alpha }) \; </math> – время, необходимое для вычисления MMT. Алгоритм разбиения на рис. 2 фактически находит множество A, которое определяет множество независимых разделителей, такое, что ни одна подзадача не содержит более четырех пятых всех антидуг исходного графа. В результате количество уровней алгоритма быстрой минимальной триангуляции не превышает <math>log_{ \frac{4}{5} }(n^2) = 2 \; log_{ \frac{4}{5} }(n)</math>, чем достигается время исполнения <math>O(n^{ \alpha } log \; n)</math>.