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

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

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

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

Пусть дан набор 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 Левкопулос и Кржнарик [7] показали, что триангуляция, длина которой отличается от длины MWT не более чем на константный множитель, может быть вычислена за полиномиальное время для произвольных множество точек. Этот результат достигается при помощи модификации так называемой жадной триангуляции. Жадная триангуляция начинается с пустого множества диагоналей и последовательно добавляет кратчайшую диагональ, не пересекающую уже добавленные ранее диагонали, до тех пор, пока не будет достигнута полная триангуляция. Было показано, что жадная триангуляция способна аппроксимировать задачу триангуляции с минимальным весом с точностью до константного коэффициента за исключением специального случая, когда «жадные» диагонали вставляются особым, очень несбалансированным образом вдоль достаточно длинной вогнутой цепи, содержащей много вершин, рядом с которой находится большое пустое пространство, не позволяющее увидеть противоположную вогнутую цепь из большого количества вершин. Было показано, что в подобных «плохих» случаях наихудшее соотношение между длинами жадной триангуляции и триангуляции с минимальным весом составляет &(*/n). Для получения триангуляции, всегда аппроксимирующей задачу MWT с константным коэффициентом, достаточно обратить внимание на этот специальный случай и избегать несбалансированного добавления диагоналей вдоль одной цепи, заменив его более сбалансированным подъемом вдоль обеих цепей. Каждое ребро, вставленное по этой технологии, оказывается почти таким же коротким, как кратчайшая диагональ, превосходя ее не более чем в 1,2 раза. Эта модифицированная триангуляция, всегда аппроксимирующая задачу MWT, была названа квази-жадной триангуляцией. Как и у исходной жадной триангуляции, ее время выполнения составляет O(n log n) [8]. Гудмундссон и Левкопулос [5] позже показали возможность распараллеливания варианта этого похода, в результате чего достигается аппроксимация MWT с константным коэффициентом за время O(log n), использующая O(n) процессоров по модели CRCW PRAM. Еще она побочная возможность алгоритма квази-жадной триангуляции заключается в том, что за линейное время можно легко выбрать подмножество ребер, чтобы получить выпуклое разбиение, не более чем на константный коэффициент отличающееся от выпуклого разбиения минимальной длины для входного множества точек. Последнее свойство исключительно важно для доказательства того, что квази-жадная триангуляция аппроксимирует задачу MWT. При доказательстве также используется уже известный результат, гласящий, что исходная, немодифицированная жадная триангуляция любого выпуклого многоугольника аппроксимирует задачу о триангуляции с минимальным весом [9]. Некоторые из результатов работ [7] и [8] можно объединить в следующей теореме:

Теорема 2. Пусть S – входной набор из n точек на плоскости. Длина квази-жадной триангуляции S, представляющей собой слегка модифицированный вариант жадной триангуляции, не более чем на константный множитель отличается от длины MWT (триангуляции с минимальным весом) S; эта квази-жадная триангуляция может быть вычислена за время O(n log n). Более того, длина немодифицированной жадной триангуляции S не более чем в O(pn) раз превышает длину MWT для S, и в наихудшем случае эта граница является асимптотически плотной.

Вычисление точной триангуляции с минимальным весом