4551
правка
Триангуляция с минимальным весом: различия между версиями
Перейти к навигации
Перейти к поиску
Триангуляция с минимальным весом (посмотреть исходный код)
Версия от 15:15, 25 сентября 2016
, 25 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
== Основные результаты == | == Основные результаты == | ||
Нахождению триангуляции с минимальным весом посвящено огромное множество работ, здесь будет упомянута только их часть. | |||
Мюльцер и Роте показали, что задача MWT является NP-полной [11]. Доказательство NP-полноты не было дано явно; оно основывалось на обширных расчетах, произведенных при помощи компьютера. Позднее Реми и Стегер предложили схему аппроксимации с квазиполиномиальным временем выполнения [12]. Эти результаты можно изложить в следующей теореме. | |||
Теорема 1. Задача нахождения триангуляции с минимальным весом (MWT) для входного множества S из n точек на плоскости является NP-полной. Однако для любой константы e > 0 триангуляция S с коэффициентом аппроксимации 1 + 6 для произвольно малой положительной константы e может быть вычислена за время nO(log 8n). | |||
Квази-жадный алгоритм триангуляции для аппроксимации задачи MWT | |||