4501
правка
Триангуляция с минимальным весом: различия между версиями
Перейти к навигации
Перейти к поиску
Триангуляция с минимальным весом (посмотреть исходный код)
Версия от 11:48, 28 сентября 2016
, 28 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
'''Вычисление точной триангуляции с минимальным весом''' | '''Вычисление точной триангуляции с минимальным весом''' | ||
Вкратце обсудим три подхода к вычислению точной триангуляции. При их выполнении предполагается возможным эффективное численное сравнение полной длины наборов прямолинейных отрезков для выбора набора с минимальным весом. Это предположение слишком упрощает картину, поскольку такое сравнение само по себе является открытым вопросом. Тем не менее, задача вычисления точной аппроксимации остается NP-полной даже при принятии этого предположения [11]. Эти три подхода различаются в части создания и выбора подзадач, которые затем решаются методами динамического программирования. | |||
Первый подход, предложенный Лингасом [ ], использует обобщенный метод вычисления оптимальных подграфов на полном евклидовом графе. Используя этот подход, можно добиться субэкспоненциального времени выполнения 2O(p n log n). Основная идея заключается в создании подзадач, решаемых методами динамического программирования. Это достигается при помощи проверки всех (подходящих) планарных сепараторов длины O(pn), разделяющих входное множество точек сбалансированным образом, и последующей рекурсивной обработки полученных подзадач. | |||
Второй подход использует алгоритмы с фиксированными параметрами. Скажем, если во внутренней части выпуклой оболочки множества S находятся всего O(log n) точек, то триангуляция с минимальным весом для S может быть вычислена за полиномиальное время [ ]. Этот поход также можно расширить для вычисления триангуляции с минимальным весом с учетом следующего ограничения: внешняя граница не обязательно является выпуклой оболочкой входных вершин, а может быть произвольным многоугольником. Некоторые из этих алгоритмов были реализованы (см. Грантсон и др. [ ]) для целей сравнения. Время выполнения методов динамического программирования обычно оказывается кубическим относительно количества точек на границе и экспоненциальным – относительно количества остальных точек. Таким образом, например, если во внутренней части выпуклого многогранника границы имеется k точек, то реализованный алгоритм вычисления точной триангуляции с минимальным весом требует O(n3 ■ 2k ■ k) времени [2]. | |||
Для решения задач большого размера применяется другой подход, использующий свойства триангуляции с минимальным весом (MWT), которые обычно помогают для случайных множеств точек определить многие ребра, которые могут входить (или не входить) в MWT. После этого можно применить алгоритм динамического программирования для поиска оставшихся MWT-ребер. Для случайных множеств, состоящих из десятков тысяч точек с равномерным распределением, можно при помощи этого подхода найти точную MWT за несколько минут [1]. | |||
== Применение == | |||