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

Мюльцер и Роте показали, что задача MWT является NP-полной [11]. Доказательство NP-полноты не было дано явно; оно основывалось на обширных расчетах, произведенных при помощи компьютера. Позднее Реми и Стегер предложили схему аппроксимации с квазиполиномиальным временем выполнения [12]. Эти результаты можно изложить в следующей теореме.

Все вышеперечисленные подходы оставляют нерешенными некоторые вопросы. Например, можно ли найти более простое доказательство NP-полноты, которое можно проверить без исполнения компьютерных программ? Было бы желательно улучшить константный коэффициент аппроксимации, который может быть достигнут за полиномиальное время (для упрощения доказательства константа, введенная в работе [7], не вычисляется явно и может быть достаточно большой, если доказательство проводится не слишком аккуратно). Есть надежда, что временную границу для схемы аппроксимации можно улучшить. Также может оказаться возможным оптимизировать алгоритмы, эффективно вычисляющие точную триангуляцию с минимальным весом для больших случайных наборов точек, таким образом, чтобы они могли эффективно решать более широкий класс задач, а не только задачи с полностью случайными наборами точек. Возможно, этой цели можно достичь при помощи сочетания этого подхода и алгоритмов с фиксированными параметрами, как в работах [2, 4], либо иными способами. Также остается открытым вопрос, можно ли еще больше улучшить субэкспоненциальный точный метод вычисления триангуляции.