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

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

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

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

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

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

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

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

Теорема 1. Задача вычисления триангуляции с минимальным весом (MWT) для входного множества S из n точек на плоскости является NP-полной. Однако для любой константы [math]\displaystyle{ \epsilon \gt 0 \; }[/math] триангуляция S с коэффициентом аппроксимации [math]\displaystyle{ 1 + \epsilon \; }[/math] для произвольно малой положительной константы [math]\displaystyle{ \epsilon \; }[/math] может быть вычислена за время [math]\displaystyle{ n^{O(log^8 \;n)} }[/math].

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

Левкопулос и Кржнарик [7] показали, что триангуляция, полная длина которой отличается от длины MWT не более чем на константный множитель, может быть вычислена за полиномиальное время для произвольных множеств точек [7]. Этот результат достигается при помощи модификации так называемой жадной триангуляции. Алгоритм жадной триангуляции начинает работу с пустого множества диагоналей и последовательно добавляет кратчайшую диагональ, не пересекающую уже добавленные ранее диагонали, до тех пор, пока не будет достигнута полная триангуляция. Было показано, что жадная триангуляция способна аппроксимировать задачу триангуляции с минимальным весом с точностью до константного коэффициента за исключением специального случая, когда «жадные» диагонали вставляются особым, крайне несбалансированным образом вдоль достаточно длинной вогнутой цепи, содержащей много вершин, рядом с которой находится большое пустое пространство, и при этом нет возможности «увидеть» противоположную вогнутую цепь из большого количества вершин. Было показано, что в подобных «плохих» случаях наихудшее соотношение между длинами жадной триангуляции и триангуляции с минимальным весом составляет [math]\displaystyle{ \Theta (\sqrt{n}) \; }[/math]. Для получения триангуляции, всегда аппроксимирующей задачу 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 не более чем в [math]\displaystyle{ O(\sqrt{n}) \; }[/math] раз превышает длину MWT для S, и в наихудшем случае эта граница является асимптотически плотной.

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

Вкратце обсудим три подхода к вычислению точной триангуляции. При их выполнении предполагается возможным эффективное численное сравнение полной длины наборов прямолинейных отрезков для выбора набора с минимальным весом. Это предположение слишком упрощает картину, поскольку такое сравнение само по себе является открытым вопросом. Тем не менее, задача вычисления точной аппроксимации остается NP-полной даже при принятии этого предположения [11]. Вышеупомянутые три подхода различаются в части создания и выбора подзадач, которые затем решаются методами динамического программирования.

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

Второй подход использует алгоритмы с фиксированными параметрами. Скажем, если во внутренней части выпуклой оболочки множества S находятся всего O(log n) точек, то триангуляция с минимальным весом для S может быть вычислена за полиномиальное время [4]. Этот подход также можно расширить для вычисления триангуляции с минимальным весом с учетом следующего ограничения: внешняя граница не обязательно является выпуклой оболочкой входных вершин, а может быть произвольным многоугольником. Некоторые из этих алгоритмов были реализованы (см. Грантсон и др. [2]) для целей сравнения. Время выполнения методов динамического программирования обычно оказывается кубическим относительно количества точек на границе и экспоненциальным – относительно количества остальных точек. Таким образом, например, если во внутренней части многогранника границы имеется k точек, то реализованный алгоритм вычисления точной триангуляции с минимальным весом требует [math]\displaystyle{ O(n^3 \cdot 2^k \cdot k) \; }[/math] времени [2].

Для решения задач большого размера применяется другой подход, использующий свойства триангуляции с минимальным весом (MWT), которые обычно помогают для случайных множеств точек определить большинство ребер, которые должны входить (или не могут входить) в MWT. После этого можно применить алгоритм динамического программирования для поиска оставшихся MWT-ребер. Для случайных множеств, состоящих из десятков тысяч точек с равномерным распределением, можно при помощи этого подхода найти точную MWT за несколько минут [1].

Применение

Задача вычисления триангуляции возникает в таких областях, как анализ методом конечных элементов, моделирование ландшафта, нарезка заготовок и численная аппроксимация [3, 6]. Триангуляция с минимальным весом привлекла внимание многих исследователей, главным образом благодаря своему естественному определению оптимальности и тому, что более тридцати лет остается серьезной задачей, статус сложности которой до сих пор не определен.

Открытые вопросы

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

Ссылка на код

Ссылка на код, использовавшийся для сравнения некоторых подходов к динамическому программированию в [2]: http://fuzzy.cs.uni-magdeburg.de/~borgelt/pointgon.html

См. также

• Быстрая минимальная триангуляция
• Жадные алгоритмы покрытия множества
• Минимальные геометрические остовные деревья
• Минимальные k-связные геометрические сети

Литература

1. Beirouti,R., Snoeyink, J.: Implementations of the LMT Heuristicfor Minimum Weight Triangulation. Symposium on Computational Geometry, pp. 96-105, Minneapolis, Minnesota, June 7-10,1998

2. Borgelt, C., Grantson, M., Levcopoulos, C.: Fixed-Parameter Algorithms for the Minimum Weight Triangulation Problem. Technical Report LU-CS-TR:2006-238, ISSN 1650-1276 Report 158. Lund University, Lund (An extended version has been submitted to IJCGA) (2006)

3. de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry - Algorithms and Applications, 2nd edn. Springer, Heidelberg (2000)

4. Grantson, M., Borgelt, C., Levcopoulos, C.: Minimum Weight Triangulation by Cutting Out Triangles. In: Proceedings 16th Annual International Symposium on Algorithms and Computation, ISAAC 2005, Sanya, China, pp. 984-994. Lecture Notes in Computer Science, vol. 3827. Springer, Heidelberg (2005)

5. Gudmundsson, J., Levcopoulos, C.: A Parallel Approximation Algorithm for Minimum Weight Triangulation. Nordic J. Comput. 7(1), 32-57 (2000)

6. Hjelle, 0., Daehlen, M.: Triangulations and Applications. In: Mathematics and Visualization, vol. IX. Springer, Heidelberg (2006). ISBN 978-3-540-33260-2

7. Levcopoulos, C., Krznaric, D.: Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation. J. Algorithms 27(2),303-338(1998)

8. Levcopoulos, C., Krznaric, D.: The Greedy Griangulation can be Computed from the Delaunay Triangulation in Linear Time. Comput.Geom. 14(4), 197-220 (1999)

9. Levcopoulos, C., Lingas, A.: On Approximation Behavior of the Greedy Triangulation for Convex Polygons. Algorithmica 2, 15-193(1987)

10. Lingas, A.: Subexponential-time algorithms for minimum weight triangulations and related problems. In: Proceed ings 10th Canadian Conference on Computational Geometry (CCCG), McGill University, Montreal, Quebec, 10-12 August 1998

11. Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. In: Proceedings 22nd Annual ACM Symposium on Computational Geometry, SoCG'06, Sedona, AZ, USA. ACM Press, New York, NY, USA (2006)

12. Remy, J., Steger, A.: A Quasi-Polynomial Time Approximation Scheme for Minimum Weight Triangulation. In: Proceedings 38th ACM Symposium on Theory of Computing (STOC'06). ACM Press, New York, NY, USA (2006)