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