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

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

История

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

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

Сложность

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

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

Хотя это NP-трудно, триангуляция с минимальным весом может быть построена за субэкспоненциальное время с помощью алгоритма динамического программирования , который рассматривает все возможные простые разделители циклов точек внутри триангуляции, рекурсивно находит оптимальную триангуляцию на каждой стороне цикла и выбирает разделитель циклов, приводящий к наименьшему общему весу. Общее время для этого метода составляет . ^[3] $O({\sqrt {n}})$ $2^{O({\sqrt {n}}\log n)}$

Приближение

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

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

Эвристика

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

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

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

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

Вариации

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

Для каждого возможного значения i от n − 1 до 1 выполните:
- Для каждого возможного значения j от i + 1 до n выполните:
  - Если ij — ребро многоугольника, установим MWT( i , j ) = length( ij )
  - В противном случае, если ij не является внутренней диагональю многоугольника, устанавливаем MWT( i , j ) = +∞
  - В противном случае установите MWT( i , j ) = length( ij ) + min _{i < k < j} MWT( i , k ) + MWT( k,j )

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

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

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

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

Примечания

^ Обзоры проблемы см. в Xu (1998), Levcopoulos (2008) и De Loera, Rambau & Santos (2010).
↑ См. также Манахер и Зобрист (1979).
^ Лингас (1998).
^ Киркпатрик (1980). Более слабая граница была дана Манахером и Зобристом (1979).
^ Семейство примеров, доказывающих, что отношение аппроксимации равно, было дано Левкопулосом (1987), а соответствующая верхняя граница — Левкопулосом и Крзнаричем (1998). Как и в случае отношения аппроксимации для триангуляции Делоне, более слабая граница была также дана Манахером и Зобристом (1979). $\Омега ({\sqrt {n}})$
^ Лингас (1986).
^ Remy & Steger (2009). Более ранние результаты по полиномиальным алгоритмам аппроксимации см. в Plaisted & Hong (1987) (логарифмическое факторное приближение) и Levcopoulos & Krznaric (1998) (постоянное факторное приближение).
^ Ченг, Голин и Цанг (1995).
^ Лингас (1987); Хит и Пеммараджу (1994).
↑ Ян, Сюй и Ю (1994).
^ Кейл (1994); Ченг, Голин и Цанг (1995); Ченг и Сюй (2001); Ху (2010).
^ Дикерсон и Монтегю (1996); Ченг, Като и Сугай (1996); Бейрути и Сноейинк (1998); Айххольцер, Ауренхаммер и Хайнц (1999).
^ Бозе, Деврой и Эванс (1996).
^ Цинь, Ван и Гун (1997); Кэпп и Джульстрем (1998).
^ Киода и др. (1997).
^ Джахани, Бигэм и Аскари (2010).
^ Хоффманн и Окамото (2004); Грантсон, Боргельт и Левкопулос (2005); Кнауэр и Спилнер (2006).
^ Ананьосту и Корней (1993); Мейер и Раппапорт (1992).
^ Эппштейн (1994).
^ Гудмундссон и Левкопулос (2007); Айххольцер и др. (2009).
^ Ленхарт и Лиотта (2002).

Ссылки

Айххольцер, Освин; Ауренхаммер, Франц ; Хакль, Томас; Спекманн, Беттина (2009), «О псевдотриангуляциях минимального веса», Computational Geometry Theory and Applications , 42 (6–7): 627–631, doi : 10.1016/j.comgeo.2008.10.002 , MR 2519380.
Айххольцер, Освин; Ауренхаммер, Франц ; Хайнц, Рейнхард (1999), «Новые результаты по подграфам MWT», Information Processing Letters , 69 (5): 215–219, doi :10.1016/S0020-0190(99)00018-6.
Анагносту, Эфтимиос; Корнейл, Дерек (1993), "Примеры задачи триангуляции минимального веса за полиномиальное время", Computational Geometry. Теория и приложения , 3 (5): 247–259, doi : 10.1016/0925-7721(93)90016-Y , MR 1251594.
Бейрути, Рональд; Снойинк, Джек (1998), «Реализации эвристики LMT для триангуляции минимального веса», Труды 14-го симпозиума ACM по вычислительной геометрии , стр. 96–105, doi : 10.1145/276884.276895 , S2CID 15102126.
Бозе, Просенджит ; Девройе, Люк; Эванс, Уильям (1996), «Бриллианты — не лучшие друзья триангуляции минимального веса», Труды 8-й Канадской конференции по вычислительной геометрии (CCCG 1996) (PDF) , стр. 68–73.
Кэпп, Керри; Джулстром, Брайант А. (1998), «Генетический алгоритм с весовым кодированием для задачи триангуляции с минимальным весом», Proc. ACM Symposium on Applied Computing , Атланта, Джорджия, США, стр. 327–331, doi :10.1145/330560.330833, S2CID 13589205, Semantic Scholar{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ).
Ченг, Сиу-Винг; Голин, Мордехай; Цанг, Дж. (1995), «Ожидаемый анализ случаев β -скелетов с применением к построению триангуляций минимального веса», Труды 7-й Канадской конференции по вычислительной геометрии (CCCG 1995) , стр. 279–284.
Cheng, Siu-Wing; Katoh, Naoki; Sugai, Manabu (1996), "Исследование LMT-скелета", Алгоритмы и вычисления , Lecture Notes in Computer Science, т. 1178, стр. 256–265, doi :10.1007/BFb0009502, ISBN 978-3-540-62048-8.
Чэн, Сиу-Вин; Сюй, Инь-Фэн (2001), «О β -скелете как подграфе триангуляции минимального веса», Теоретическая информатика , 262 (1–2): 459–471, doi : 10.1016/S0304-3975(00)00318-2.
Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010), «3.2.3 Жадные и минимально-весовые триангуляции», Триангуляции: структуры для алгоритмов и приложений , Алгоритмы и вычисления в математике, т. 25, Springer, стр. 102–107, ISBN 978-3-642-12970-4.
Дикерсон, Мэтью Т .; Монтегю, Марк Х. (1996), «(Обычно?) Связный подграф триангуляции минимального веса», Труды 12-го симпозиума ACM по вычислительной геометрии , стр. 204–213, doi :10.1145/237218.237364, S2CID 18962760.
Дюппе, РД; Gottschalk, HJ (1970), «Автоматическая интерполяция фон Isolinien bei willkürlich verteilten Stützpunkten», Allgemeine Vermessungs-Nachrichten , 77 : 423–426. Как цитируют Mulzer & Rote (2008) и Remy & Steger (2009).
Эппштейн, Дэвид (1994), «Аппроксимация триангуляции Штейнера с минимальным весом» (PDF) , Дискретная и вычислительная геометрия , 11 (2): 163–191, doi : 10.1007/BF02574002 , MR 1254088.
Гэри, М. Р.; Джонсон , Д. С. (1979), Компьютеры и неразрешимость: Руководство по теории NP-полноты , Сан-Франциско, Калифорния: WH Freeman, Задача OPEN12, стр. 288, ISBN 0-7167-1045-5, МР 0519066.
Гилберт, П.Д. (1979), Новые результаты в области плоских триангуляций , Отчет R-850, Урбана, Иллинойс: Лаборатория координированной науки, Университет Иллинойса.
Грантсон, М.; Боргельт, К.; Левкопулос, К. (2005), «Триангуляция минимального веса путем вырезания треугольников», Труды 16-го Международного симпозиума по алгоритмам и вычислениям , стр. 984–994.
Гудмундссон, Иоахим; Левкопулос, Христос (2007), «Псевдотриангуляции минимального веса», Computational Geometry Theory and Applications , 38 (3): 139–153, doi : 10.1016/j.comgeo.2007.05.004 , MR 2352529.
Хит, Л. С.; Пеммараджу, С. В. (1994), «Новые результаты для задачи триангуляции минимального веса», Algorithmica , 12 (6): 533–552, doi : 10.1007/BF01188718, hdl : 10919/19701 , MR 1297812, S2CID 21160664.
Хоффманн, М.; Окамото, Й. (2004), «Проблема триангуляции минимального веса с несколькими внутренними точками», Труды 1-го Международного семинара по параметризованным и точным вычислениям , стр. 200–212.
Ху, Шиян (2010), «Новая асимметричная область включения для триангуляции минимального веса», Журнал глобальной оптимизации , 46 (1): 63–73, CiteSeerX 10.1.1.377.6164 , doi :10.1007/s10898-009-9409-z, MR 2566136, S2CID 869128.
Джахани, М.; Бигхэм, Б.С.; Аскари, А. (2010), «Алгоритм муравьиной колонии для триангуляции минимального веса», Международная конференция по вычислительной науке и ее приложениям (ICCSA) , стр. 81–85, doi :10.1109/ICCSA.2010.38, S2CID 11790811, Semantic Scholar.
Кейл, Дж. Марк (1994), «Вычисление подграфа триангуляции минимального веса», Computational Geometry: Theory & Applications , 4 (1): 18–26, doi : 10.1016/0925-7721(94)90014-0.
Киркпатрик, Дэвид Г. (1980), «Заметка о Делоне и оптимальных триангуляциях», Information Processing Letters , 10 (3): 127–128, doi :10.1016/0020-0190(80)90062-9, MR 0566856.
Клинчек, Г. Т. (1980), «Минимальные триангуляции многоугольных областей», Annals of Discrete Mathematics , 9 : 121–123, doi :10.1016/s0167-5060(08)70044-x, ISBN 9780444861115.
Кнауэр, Кристиан; Шпильнер, Андреас (2006), «Алгоритм с фиксированными параметрами для задачи триангуляции минимального веса на основе небольших разделителей графов», Графовые теоретические концепции в информатике , Lecture Notes in Computer Science, т. 4271, Берлин: Springer, стр. 49–57, doi :10.1007/11917496_5, ISBN 978-3-540-48381-6, МР 2290717.
Киода, Ёсиаки; Имаи, Кейко; Такеучи, Фумихико; Таджима, Акира (1997), «Подход ветвей и отсечений для триангуляции минимального веса», Алгоритмы и вычисления (Сингапур, 1997) , Lecture Notes in Computer Science, т. 1350, Берлин: Springer, стр. 384–393, doi :10.1007/3-540-63890-3_41, ISBN 978-3-540-63890-2, МР 1651067.
Ленхарт, Уильям; Лиотта, Джузеппе (2002), «Проблема рисования для триангуляций минимального веса», Теоретическая информатика , 270 (1–2): 261–286, doi :10.1016/S0304-3975(00)00383-2, MR 1871072.
Левкопулос, Христос (1987), «Нижняя граница Ω(√ n ) для неоптимальности жадной триангуляции», Information Processing Letters , 25 (4): 247–251, doi :10.1016/0020-0190(87)90170-0, MR 0896144.
Левкопулос, Христос (2008), «Триангуляция минимального веса», в Као, Мин-Ян (ред.), Энциклопедия алгоритмов , Springer, стр. 546–548, ISBN 978-0-387-30770-1.
Levcopoulos, C.; Krznaric, D. (1998), «Квазижадные триангуляции, аппроксимирующие триангуляцию минимального веса» (PDF) , Журнал алгоритмов , 27 (2): 303–338, doi :10.1006/jagm.1997.0918, MR 1622398, S2CID 13991653.
Лингас, Анджей (1986), «Триангуляции Гриди и Делоне неплохи в среднем случае», Information Processing Letters , 22 (1): 25–31, doi :10.1016/0020-0190(86)90038-4.
Лингас, Анджей (1987), «Новая эвристика для триангуляции минимального веса», Журнал SIAM по алгебраическим и дискретным методам , 8 (4): 646–658, doi :10.1137/0608053, MR 0918066.
Лингас, Анджей (1998), «Субэкспоненциальные алгоритмы для триангуляции минимального веса и связанных с ними проблем», Труды 10-й Канадской конференции по вычислительной геометрии (CCCG'98).
Ллойд, Э. (1977), «О триангуляциях множества точек на плоскости», Труды 18-го симпозиума IEEE по основам компьютерной науки , стр. 228–240.
Манахер, Гленн К.; Зобрист, Альберт Л. (1979), «Ни жадная триангуляция, ни триангуляция Делоне плоского множества точек не приближают оптимальную триангуляцию», Information Processing Letters , 9 (1): 31–34, doi :10.1016/0020-0190(79)90104-2, MR 0537055.
Мейер, Хенк; Раппапорт, Дэвид (1992), «Вычисление триангуляции минимального веса для набора линейно упорядоченных точек», Information Processing Letters , 42 (1): 35–38, doi :10.1016/0020-0190(92)90129-J, MR 1160443.
Мульцер, Вольфганг; Роте, Гюнтер (2008), «Триангуляция с минимальным весом NP-трудна», Журнал ACM , 55 (2), Статья A11, arXiv : cs.CG/0601002 , doi : 10.1145/1346330.1346336, S2CID 1658062.
Плейстед, Д.А.; Хонг, Дж. (1987), «Эвристический алгоритм триангуляции», Журнал алгоритмов , 8 (3): 405–437, doi : 10.1016/0196-6774(87)90020-4.
Qin, Kaihuai; Wang, Wenping; Gong, Minglun (1997), "Генетический алгоритм для триангуляции минимального веса", Международная конференция IEEE по эволюционным вычислениям , стр. 541–546, doi : 10.1109/ICEC.1997.592370, hdl : 10722/45578 , S2CID 18775737, Semantic Scholar.
Реми, Ян; Стегер, Анжелика (2009), «Квазиполиномиальная схема аппроксимации времени для триангуляции минимального веса», Журнал ACM , 56 (3), Статья A15, doi : 10.1145/1516512.1516517, S2CID 1781658.
Шамос, MI ; Хои, DJ (1975), «Проблемы с ближайшими точками», Труды 16-го симпозиума IEEE по основам компьютерной науки (PDF) , стр. 151–162.
Ван, Цао Ань; Ян, Ботинг (2001), «Нижняя граница для β -скелета, принадлежащего триангуляции минимального веса», Computational Geometry: Theory & Applications , 19 (1): 35–46, doi :10.1016/S0925-7721(01)00008-6.
Сюй, Инь-Фэн (1998), «Триангуляции минимального веса», Справочник по комбинаторной оптимизации, т. 2 , Бостон, Массачусетс: Kluwer Academic Publishers, стр. 617–634, MR 1665412.
Yang, Bo Ting; Xu, Yin Feng; You, Zhao Yong (1994), "Алгоритм разложения цепи для доказательства свойства на триангуляциях минимального веса", в Du, Ding-Zhu; Zhang, Xiang-Sun (ред.), Алгоритмы и вычисления: 5-й международный симпозиум, ISAAC '94, Пекин, КНР, 25–27 августа 1994 г., Труды , Заметки лекций по информатике, т. 834, Берлин: Springer, стр. 423–427, doi :10.1007/3-540-58325-4_207, ISBN 978-3-540-58325-7, г-н 1316441.

Внешние ссылки

Триангуляция минимального веса с использованием исходного кода скелета LMT