Триангуляция минимального веса
В вычислительной геометрии и информатике проблема триангуляции минимального веса — это проблема нахождения триангуляции минимальной общей длины ребра. [1] То есть входной многоугольник или выпуклая оболочка множества входных точек должны быть разделены на треугольники, пересекающиеся ребрами и вершинами, таким образом, чтобы минимизировать сумму периметров треугольники. Задача является NP-сложной для входных данных набора точек, но может быть аппроксимирована с любой желаемой степенью точности. Для входных полигонов это может быть решено точно за полиномиальное время. Триангуляцию минимального веса также иногда называют оптимальной триангуляцией ..
Проблема триангуляции минимального веса набора точек была поставлена Дюппе и Готтшалком (1970) , которые предложили ее применение для построения триангулированных нерегулярных сетевых моделей контуров суши и использовали жадную эвристику для ее аппроксимации. Шамос и Хоуи (1975) предположили, что триангуляция минимального веса всегда совпадает с триангуляцией Делоне , но это было быстро опровергнуто Ллойдом (1977) , и Киркпатрик (1980) действительно показал, что веса двух триангуляций могут различаться линейным коэффициентом. . [2]
Проблема триангуляции минимального веса стала печально известной, когда Гэри и Джонсон (Garey & Johnson, 1979) включили ее в список открытых проблем в своей книге по NP-полноте , и многие последующие авторы опубликовали по ней частичные результаты. Наконец, Mulzer & Rote (2008) показали, что он является NP-трудным, а Remy & Steger (2009) показали, что точные приближения к нему могут быть построены эффективно.
Вес триангуляции множества точек на евклидовой плоскости определяется как сумма длин его ребер. Его вариант решения - это проблема определения того, существует ли триангуляция веса меньше заданного веса; Mulzer & Rote (2008) доказало, что он является NP-трудным . Их доказательство основано на сокращении от PLANAR-1-IN-3-SAT, частного случая булевой проблемы выполнимости, в которой 3-CNF , граф которой является планарным , принимается, когда оно имеет истинностное назначение, которое удовлетворяет ровно одному литералу в каждом предложении . . Доказательство использует сложные гаджеты и включает в себякомпьютерная помощь для проверки правильного поведения этих гаджетов.
Неизвестно, является ли задача решения триангуляции минимального веса NP-полной , так как это зависит от известной открытой проблемы, может ли сумма радикалов быть вычислена за полиномиальное время. Однако Малцер и Роте отмечают, что задача является NP-полной, если веса ребер округлены до целых значений.
Хотя триангуляция с минимальным весом является NP-сложной, она может быть построена за субэкспоненциальное время с помощью алгоритма динамического программирования , который рассматривает все возможные простые разделители циклов точек внутри триангуляции, рекурсивно находит оптимальную триангуляцию на каждой стороне цикла и выбирает разделитель циклов. приводит к наименьшему общему весу. Общее время для этого метода составляет . [3]
