Триангуляция минимального веса - Minimum-weight triangulation

Три возможных триангуляции одного и того же многоугольника. Центральная триангуляция имеет меньший вес (сумма периметров).

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

История

Задача триангуляции минимального веса множества точек была поставлена Дюпп и Готтшалк (1970), который предложил его применение для строительства триангулированная нерегулярная сеть модели земельных участков и использовали жадный эвристический чтобы приблизить это. Шамос и Хоуи (1975) предположил, что триангуляция минимального веса всегда совпадает с Триангуляция Делоне, но это было быстро опровергнуто Ллойд (1977), и действительно Киркпатрик (1980) показал, что веса двух триангуляций могут различаться в линейный коэффициент.[2]

Проблема триангуляции минимального веса стала печально известной, когда Гэри и Джонсон (1979) включили его в список открытых проблем в своей книге по NP-полнота, и многие последующие авторы опубликовали частичные результаты по нему. Ну наконец то, Mulzer & Rote (2008) показал, что это NP-сложно, и Реми и Стегер (2009) показал, что точные приближения к нему могут быть эффективно построены.

Сложность

Вес триангуляции набора точек в Евклидова плоскость определяется как сумма длин его ребер. Его вариант решения проблема определения, существует ли триангуляция веса меньше данного веса; это было доказано NP-жесткий к Mulzer & Rote (2008). Их доказательство снижение из PLANAR-1-IN-3-SAT, частный случай Проблема логической выполнимости в котором 3-CNF чей график планарный принимается, когда у него есть задание истинности, которое точно удовлетворяет один литерал в каждом предложении. Доказательство использует сложные гаджеты, и включает компьютерная помощь для проверки правильного поведения этих гаджетов.

Неизвестно, является ли задача решения триангуляции минимального веса НП-полный, поскольку это зависит от известной открытой проблемы, сумма радикалов может быть вычислено за полиномиальное время. Однако Малзер и Роте отмечают, что проблема NP-полная, если веса ребер округляются до целых значений.

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

Приближение

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

Результат Мульцера и Роте о твердости также подразумевает NP-трудность нахождения приближенного решения с относительной ошибкой приближения не более O (1 / n2). Таким образом, полностью полиномиальная схема аппроксимации для минимального веса триангуляция маловероятна. Однако возможна квазиполиномиальная схема аппроксимации: для любой постоянной ε> 0 решение с отношением аппроксимации 1 + ε может быть найдено в квазиполиномиальное время exp (O ((logп)9).[7]

Эвристика

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

Граф, образованный соединением двух точек, когда они являются ближайшими соседями друг друга, обязательно является подграфом триангуляции минимального веса.[10] Однако этот граф взаимных ближайших соседей является соответствие, а значит, никогда не подключается. Связанное с этим направление исследований обнаруживает большие подграфы триангуляции минимального веса с помощью круговой β-скелеты, геометрические графы, образованные включением ребра между двумя точками ты и v когда не существует третьей точки ш образуя угол uwv больше некоторого параметра θ. Было показано, что при достаточно малых значениях θ сформированный таким образом граф является подграфом триангуляции минимального веса.[11] Однако выбор θ, необходимый для обеспечения того, чтобы он был меньше угла θ = 90ª, для которого β-скелет всегда подключен.

Более сложная техника, названная LMT-скелетом, была предложена Дикерсон и Монтегю (1996). Он формируется с помощью итеративного процесса, в котором поддерживаются два набора ребер: набор ребер, о которых известно, что они принадлежат триангуляции минимального веса, и набор ребер, которые являются кандидатами на принадлежность к ней. Первоначально набор известных ребер инициализируется выпуклый корпус входа, а все оставшиеся пары вершин образуют ребра-кандидаты. Затем на каждой итерации процесса построения ребра-кандидаты удаляются всякий раз, когда нет пары треугольников, образованных оставшимися ребрами, образующими четырехугольник, для которого ребро-кандидат является самой короткой диагональю, и ребра-кандидаты перемещаются в набор известных ребер. когда нет другого края кандидата, который их пересекает. LMT-скелет определяется как набор известных ребер, созданных после того, как этот процесс перестает вносить какие-либо изменения. Гарантируется, что это подграф триангуляции минимального веса, его можно эффективно построить, и в экспериментах с наборами до 200 точек он часто соединялся.[12] Однако было показано, что в среднем для больших точечных наборов он имеет линейное количество компонентов связности.[13]

Другие эвристики, которые были применены к задаче триангуляции минимального веса, включают: генетические алгоритмы[14] ветвь и переплет,[15] и алгоритмы оптимизации муравьиной колонии.[16]

Вариации

А триангуляция многоугольника минимального веса можно построить за кубическое время, используя динамическое программирование подход, о котором независимо сообщила Гилберт (1979) и Клинчек (1980). В этом методе вершины пронумерованы последовательно вокруг границы многоугольника, и для каждой диагонали от вершины я к вершине j который лежит внутри многоугольника, оптимальная триангуляция рассчитывается с учетом всех возможных треугольников ijk внутри многоугольника, добавляя веса оптимальных триангуляций под диагоналями ik и jk, и выбирая вершину k что приводит к минимальному общему весу. То есть, если MWT (я,j) обозначает вес триангуляции минимального веса многоугольника под ребром ij, то общий алгоритм выполняет следующие шаги:

  • Для каждого возможного значения я, из п - от 1 до 1, сделать:
    • Для каждого возможного значения j, из я +1 к п, делать:
      • Если ij - край многоугольника, положим MWT (я,j) = длина (ij)
      • Иначе, если ij не является внутренней диагональю многоугольника, установите MWT (я,j) = +∞
      • Иначе установите MWT (я,j) = длина (ij) + миня < k < j MWT (я,k) + MWT (k, j)

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

Подобные методы динамического программирования также могут быть адаптированы к входам набора точек, где все точки, кроме постоянного, находятся на выпуклый корпус входа,[17] и наборов точек, которые лежат на постоянном количестве вложенных выпуклых многоугольников или на постоянном количестве линий, две из которых не пересекаются внутри выпуклой оболочки.[18]

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

Смежные проблемы, которые также изучались, включают построение минимального веса псевдотриангуляции[20] и характеристика графиков триангуляций минимального веса.[21]

Примечания

  1. ^ Для обзоров проблемы см. Сюй (1998), Левкопулос (2008), и Де Лоэра, Рамбау и Сантос (2010).
  2. ^ Смотрите также Манахер и Зобрист (1979).
  3. ^ Лингасы (1998).
  4. ^ Киркпатрик (1980). Более слабая оценка была дана Манахер и Зобрист (1979).
  5. ^ Семейство примеров, доказывающих, что коэффициент аппроксимации равен был дан Левкопулос (1987), а соответствующая верхняя граница равна Левкопулос и Кшнарич (1998). Как и в случае отношения аппроксимации для триангуляции Делоне, более слабая оценка также была дана Манахер и Зобрист (1979).
  6. ^ Лингас (1986).
  7. ^ Реми и Стегер (2009). Более ранние результаты по алгоритмам полиномиальной аппроксимации см. Плейстед и Хонг (1987) (приближение лог-фактора) и Левкопулос и Кшнарич (1998) (приближение постоянного фактора).
  8. ^ Ченг, Голин и Цанг (1995).
  9. ^ Лингас (1987); Хит и Пеммараджу (1994).
  10. ^ Ян, Сюй и Ю (1994).
  11. ^ Кейл (1994); Ченг, Голин и Цанг (1995); Ченг и Сюй (2001); Ху (2010).
  12. ^ Дикерсон и Монтегю (1996); Ченг, Като и Сугай (1996); Бейрути и Snoeyink (1998); Айхольцер, Ауренхаммер и Хайнц (1999).
  13. ^ Бозе, Деврой и Эванс (1996).
  14. ^ Цинь, Ван и Гун (1997); Кэпп и Джулстрем (1998).
  15. ^ Kyoda et al. (1997).
  16. ^ Джахани, Бигхэм и Аскари (2010).
  17. ^ Хоффманн и Окамото (2004); Грантсон, Боргельт и Левкопулос (2005); Knauer & Spillner (2006).
  18. ^ Анагносту и Корней (1993); Мейер и Раппапорт (1992).
  19. ^ Эппштейн (1994).
  20. ^ Гудмундссон и Левкопулос (2007); Aichholzer et al. (2009).
  21. ^ Ленхарт и Лиотта (2002).

Рекомендации

внешняя ссылка