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

Первый подход, предложенный Лингасом [10], использует обобщенный метод вычисления оптимальных подграфов на полном евклидовом графе. Используя этот подход, можно добиться субэкспоненциального времени выполнения 2O(p n log n). Основная идея заключается в создании подзадач, решаемых методами динамического программирования. Это достигается при помощи проверки всех (подходящих) планарных сепараторов длины O(pn), разделяющих входное множество точек сбалансированным образом, и последующей рекурсивной обработки полученных подзадач.

Второй подход использует алгоритмы с фиксированными параметрами. Скажем, если во внутренней части выпуклой оболочки множества S находятся всего O(log n) точек, то триангуляция с минимальным весом для S может быть вычислена за полиномиальное время [ ]. Этот подход также можно расширить для вычисления триангуляции с минимальным весом с учетом следующего ограничения: внешняя граница не обязательно является выпуклой оболочкой входных вершин, а может быть произвольным многоугольником. Некоторые из этих алгоритмов были реализованы (см. Грантсон и др. [ ]) для целей сравнения. Время выполнения методов динамического программирования обычно оказывается кубическим относительно количества точек на границе и экспоненциальным – относительно количества остальных точек. Таким образом, например, если во внутренней части многогранника границы имеется k точек, то реализованный алгоритм вычисления точной триангуляции с минимальным весом требует O(n3 ■ 2k ■ k) времени [2].