Триангуляция с минимальным весом

Ключевые слова и синонимы

Триангуляция минимальной длины

Постановка задачи

Пусть дан набор S из n точек на евклидовой плоскости. Триангуляция T набора S представляет собой максимальное множество непересекающихся прямолинейных сегментов, конечные точки которых принадлежат S. Вес T определяется как полная евклидова длина всех ребер T. Триангуляция S, обеспечивающая минимальный вес, называется триангуляцией с минимальным весом, и обозначается MWT (minimum weight triangulation).

Основные результаты

Нахождению триангуляции с минимальным весом посвящено огромное множество работ, здесь будет упомянута только их часть.

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

Теорема 1. Задача нахождения триангуляции с минимальным весом (MWT) для входного множества S из n точек на плоскости является NP-полной. Однако для любой константы e > 0 триангуляция S с коэффициентом аппроксимации 1 + 6 для произвольно малой положительной константы e может быть вычислена за время nO(log 8n).

Квази-жадный алгоритм триангуляции для аппроксимации задачи MWT