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

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

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

История

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

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

Сложность

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

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

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

Приближение

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

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

Эвристика

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

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

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

Другие эвристики, которые применялись к задаче триангуляции минимального веса, включают генетические алгоритмы. ветвь и граница , и алгоритмы оптимизации колонии муравьев .

Вариации

минимального Триангуляция многоугольника веса может быть построена за кубическое время с использованием подхода динамического программирования , о котором независимо сообщили Гилберт (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 ).

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

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

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

Ссылки

• Айххольцер, Освин; Ауренхаммер, Франц ; Хакл, Томас; Спекманн, Беттина (2009), «О псевдотриангуляциях с минимальным весом», Теория и приложения вычислительной геометрии , 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), «Примеры задачи триангуляции минимального веса за полиномиальное время», Вычислительная геометрия. Теория и приложения , 3 (5): 247–259, doi : 10.1016/0925-7721(93)90016-Y , MR   1251594 .
• Бейрути, Рональд; Снойинк, Джек (1998), "Реализация эвристики LMT для триангуляции с минимальным весом", Proc. 14-й симпозиум ACM по вычислительной геометрии , стр. 96–105, doi : 10.1145/276884.276895 , S2CID   15102126 .
• Бозе, Просенджит ; Деврой, Люк; Эванс, Уильям (1996), «Бриллианты не являются лучшим другом триангуляции минимального веса», Proc. 8-я Канадская конференция по вычислительной геометрии (CCCG 1996) (PDF) , стр. 68–73 .
• Кэпп, Керри; Джулстрем, Брайант А. (1998), "Генетический алгоритм с весовым кодированием для задачи триангуляции с минимальным весом", Proc. Симпозиум ACM по прикладным вычислениям , Атланта, Джорджия, США, стр. 327–331, номер номера : 10.1145/330560.330833 , S2CID   13589205 , ученый-семантик. {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .
• Ченг, Сиу-Винг; Голин, Мордехай; Цанг, Дж. (1995), "Анализ ожидаемых случаев β -скелетов с применением к построению триангуляций минимального веса", Proc. 7-я Канадская конференция по вычислительной геометрии (CCCG 1995) , стр. 279–284 .
• Ченг, Сиу-Винг; Като, Наоки; Сугай, Манабу (1996), «Исследование LMT-скелета», «Алгоритмы и вычисления » , Конспекты лекций по информатике, том. 1178, стр. 256–265, номер документа : 10.1007/BFb0009502 , ISBN.  978-3-540-62048-8 .
• Ченг, Сиу-Винг; Сюй, Инь-Фэн (2001), «О β -скелете как подграфе триангуляции минимального веса», Theoretical Computer Science , 262 (1–2): 459–471, doi : 10.1016/S0304-3975(00)00318 -2 .
• Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010), «3.2.3 Жадные триангуляции и триангуляции с минимальным весом», Триангуляции: структуры для алгоритмов и приложений , Алгоритмы и вычисления в математике, том. 25, Спрингер, стр. 102–107, ISBN.  978-3-642-12970-4 .
• Дикерсон, Мэтью Т .; Монтегю, Марк Х. (1996), «Связный (обычно?) Подграф триангуляции минимального веса», Proc. 12-й симпозиум ACM по вычислительной геометрии , стр. 204–213, doi : 10.1145/237218.237364 , S2CID   18962760 .
• Дюппе, РД; Gottschalk, HJ (1970), «Автоматическая интерполяция изолиний в произвольно распределенных базовых точках», Allgemeine Vermessungs-Nachrichten , 77 : 423–426 . По данным Mulzer & Rote (2008) и Remy & Steger (2009) .
• Эппштейн, Дэвид (1994), «Аппроксимация минимальной весовой триангуляции Штейнера» (PDF) , Дискретная и вычислительная геометрия , 11 (2): 163–191, doi : 10.1007/BF02574002 , MR   1254088 .
• Гэри, MR ; Джонсон, Д.С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , Сан-Франциско, Калифорния: WH Freeman, Проблема OPEN12, стр. 288 , ISBN  0-7167-1045-5 , МР   0519066 .
• Гилберт, П.Д. (1979), Новые результаты в плоских триангуляциях , Отчет R-850, Урбана, Иллинойс: Координированная научная лаборатория, Университет Иллинойса .
• Грантсон, М.; Боргельт, К.; Левкопулос, К. (2005), «Триангуляция минимального веса путем вырезания треугольников», Proc. 16-й Международный симпозиум по алгоритмам и вычислениям , стр. 984–994 .
• Гудмундссон, Иоахим; Левкопулос, Христос (2007), «Псевдотриангуляции с минимальным весом», Теория вычислительной геометрии и приложения , 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), «Задача триангуляции минимального веса с небольшим количеством внутренних точек», Proc. 1-й международный семинар по параметризованным и точным вычислениям , стр. 200–212 .
• Ху, Шиян (2010), «Новая асимметричная область включения для триангуляции с минимальным весом», Journal of Global Optimization , 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 , Семантика Ученый .
• Кейл, Дж. Марк (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), «Минимальные триангуляции полигональных областей», Анналы дискретной математики , 9 : 121–123, doi : 10.1016/s0167-5060(08)70044-x , ISBN  9780444861115 .
• Кнауэр, Кристиан; Спилнер, Андреас (2006), «Алгоритм с фиксированным параметром для задачи триангуляции минимального веса на основе небольших разделителей графов», Теоретико-графовые концепции в информатике , Конспекты лекций по информатике, том. 4271, Берлин: Springer, стр. 49–57, номер документа : 10.1007/11917496_5 , ISBN.  978-3-540-48381-6 , МР   2290717 .
• Кёда, Ёсиаки; Имаи, Кейко; Такеучи, Фумихико; Тадзима, Акира (1997), «Подход ветвей и разрезов для триангуляции минимального веса», Алгоритмы и вычисления (Сингапур, 1997) , Конспекты лекций по информатике, том. 1350, Берлин: Springer, стр. 384–393, номер документа : 10.1007/3-540-63890-3_41 , ISBN.  978-3-540-63890-2 , МР   1651067 .
• Ленхарт, Уильям; Лиотта, Джузеппе (2002), «Проблема рисования для триангуляций с минимальным весом», Theoretical Computer Science , 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 , МР   0896144 .
• Левкопулос, Христос (2008), «Триангуляция минимального веса», в Као, Минг-Янг (редактор), Энциклопедия алгоритмов , Springer, стр. 546–548, ISBN  978-0-387-30770-1 .
• Левкопулос, К.; Крзнарик, Д. (1998), «Квазижадные триангуляции, аппроксимирующие триангуляцию с минимальным весом» (PDF) , Journal of Algorithms , 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 Journal on Algebraic and Discrete Methods , 8 (4): 646–658, doi : 10.1137/0608053 , MR   0918066 .
• Лингас, Анджей (1998), «Алгоритмы субэкспоненциального времени для триангуляций минимального веса и связанных с ними проблем», Труды 10-й Канадской конференции по вычислительной геометрии (CCCG'98) .
• Ллойд, Э. (1977), «О триангуляциях множества точек на плоскости», Proc. 18-й симпозиум IEEE по основам информатики , стр. 228–240 .
• Маначер, Гленн К.; Зобрист, Альберт Л. (1979), «Ни жадная триангуляция, ни триангуляция Делоне плоского набора точек не приближают оптимальную триангуляцию», Information Processing Letters , 9 (1): 31–34, doi : 10.1016/0020-0190 (79 )90104-2 , МР   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), «Эвристический алгоритм триангуляции», Journal of Algorithms , 8 (3): 405–437, doi : 10.1016/0196-6774(87)90020-4 .
• Цинь, Кайхуай; Ван, Вэньпин; Гонг, Минглун (1997), «Генетический алгоритм триангуляции минимального веса», Международная конференция IEEE по эволюционным вычислениям , стр. 541–546, doi : 10.1109/ICEC.1997.592370 , hdl : 10722/45578 , S2CID   18775737 , ученый-семантик .
• Реми, Ян; Стегер, Анжелика (2009), «Схема квазиполиномиальной аппроксимации времени для триангуляции с минимальным весом», Журнал ACM , 56 (3), статья A15, doi : 10.1145/1516512.1516517 , S2CID   1781658 .
• Шамос, Мичиган ; Хоуи, ди-джей (1975), «Задачи ближайшей точки», Proc. 16-й симпозиум IEEE по основам информатики (PDF) , стр. 151–162 .
• Ван, Цао Ань; Ян, Ботинг (2001), «Нижняя оценка β- скелета, принадлежащего триангуляциям минимального веса», Computational Geometry: Theory & Applications , 19 (1): 35–46, doi : 10.1016/S0925-7721(01)00008- 6 .
• Сюй, Инь-Фэн (1998), «Триангуляции с минимальным весом», Справочник по комбинаторной оптимизации, Vol. 2 , Бостон, Массачусетс: Kluwer Academic Publishers, стр. 617–634, MR   1665412 .
• Ян, Бо Тин; Сюй, Инь Фэн; Ю, Чжао Юн (1994), «Алгоритм разложения цепочки для доказательства свойства триангуляции с минимальным весом», в Ду, Дин-Чжу; Чжан, Сян-Сунь (ред.), Алгоритмы и вычисления: 5-й международный симпозиум, ISAAC '94, Пекин, КНР, 25–27 августа 1994 г., Труды , конспекты лекций по информатике, том. 834, Берлин: Springer, стр. 423–427, номер документа : 10.1007/3-540-58325-4_207 , ISBN.  978-3-540-58325-7 , МР   1316441 .

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

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