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

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

История [ править ]

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

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

Сложность [ править ]

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

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

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

Приближение [ править ]

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

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

Эвристика [ править ]

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

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

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

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

Варианты [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]

  • Айххольцер, Освин; Ауренхаммер, Франц ; Хакл, Томас; Speckmann, Беттина (2009), "О минимальном весе псевдо-триангуляции", Вычислительная теория Геометрия и приложения , 42 (6-7): 627-631, DOI : 10.1016 / j.comgeo.2008.10.002 , МР  2519380.
  • Айххольцер, Освин; Ауренхаммер, Франц ; Хайнц, Рейнхард (1999), «Новые результаты по подграфам MWT», Письма об обработке информации , 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 , МР  1251594.
  • Бейрути, Рональд; Snoeyink, Джек (1998), "Реализации эвристики LMT для триангуляции минимального веса", Proc. Четырнадцатый ACM симпозиум по вычислительной геометрии . С. 96-105, DOI : 10,1145 / 276884,276895.
  • Бозе, Просенджит ; Деврой, Люк; Эванс, Уильям (1996), «Бриллианты - не лучший друг триангуляции с минимальным весом», Proc. 8-я Канадская конференция по вычислительной геометрии (CCCG 1996) (PDF) , стр. 68–73.
  • Капп, Керри; Джулстром, Брайант А. (1998), "Весовой генетический алгоритм для задачи триангуляции минимального веса", Proc. ACM симпозиум по прикладной вычислительной ., Атланта, Джорджия, США, стр 327-331, DOI : 10,1145 / 330560,330833 , Semantic Scholar.
  • Ченг, Сиу-Винг; Голин, Мардохей; Цанг, Дж. (1995), "Анализ ожидаемых случаев β- скелетов с приложениями к построению триангуляций минимального веса", Proc. 7-я Канадская конференция по вычислительной геометрии (CCCG 1995) , стр. 279–284..
  • Ченг, Сиу-Винг; Като, Наоки; Сугай, Манабу (1996), «Исследование LMT-скелета», Алгоритмы и вычисления , Лекционные заметки по информатике, 1178 , стр. 256–265, doi : 10.1007 / BFb0009502.
  • Ченг, Сиу-Винг; Сюй Инь-Feng (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), "(обычно?) Связный подграф триангуляции минимального веса", Proc. 12 ACM симпозиум по вычислительной геометрии . С. 204-213, DOI : 10,1145 / 237218,237364.
  • Дюппе, РД; Gottschalk, HJ (1970), "Automatische Interpolation von Isolinien bei willkürlich verteilten Stützpunkten", Allgemeine Vermessungs-Nachrichten , 77 : 423–426. Цитируется Mulzer & Rote (2008) и Remy & Steger (2009) .
  • Eppstein, Дэвид (1994), "Аппроксимация минимального веса Steiner триангуляции" (PDF) , Дискретная и Вычислительная геометрия , 11 (2): 163-191, DOI : 10.1007 / BF02574002 , МР  1254088 CS1 maint: discouraged parameter (link).
  • Garey, MR ; Джонсон, Д.С. (1979), « Компьютеры и несговорчивость: руководство по теории NP- полноты», Сан-Франциско, Калифорния: WH Freeman, Problem OPEN12, p. 288 , ISBN 0-7167-1045-5, MR  0519066.
  • Гилберт, PD (1979), Новые результаты в плоских триангуляциях , Отчет R-850, Урбана, Иллинойс: Скоординированная научная лаборатория, Университет Иллинойса.
  • Grantson, M .; Borgelt, C .; Левкопулос, К. (2005), "Триангуляция минимального веса путем вырезания треугольников", Proc. 16-й Международный симпозиум по алгоритмам и вычислениям , стр. 984–994..
  • Гудмундссон, Иоахим; Levcopoulos, Christos (2007), "Минимальный вес псевдо-триангуляции", Вычислительная теория геометрии и приложений , 38 (3): 139-153, DOI : 10.1016 / j.comgeo.2007.05.004 , МР  2352529.
  • Хит, LS; Пеммараджу, С. В. (1994), "Новые результаты для задачи триангуляции минимального веса" , Algorithmica , 12 (6): 533-552, DOI : 10.1007 / BF01188718 , МР  1297812.
  • Hoffmann, M .; Окамото, Ю. (2004), "Задача триангуляции минимального веса с несколькими внутренними точками", Proc. 1-й международный семинар по параметризованным и точным вычислениям , стр. 200–212.
  • Х, Шиян (2010), "Новая асимметричное включение область для минимального веса триангуляции", журнал глобальной оптимизации , 46 (1): 63-73, CiteSeerX  10.1.1.377.6164 , DOI : 10.1007 / s10898-009-9409- z , Руководство пользователя  2566136.
  • Джахани, М .; Бигхэм, BS; Аскари, A. (2010), "Муравей алгоритм колонии для минимального веса триангуляции", Международная конференция по вычислительной науке и ее приложения (ICCSA) . С. 81-85, DOI : 10,1109 / ICCSA.2010.38 , Semantic Scholar.
  • Кейл, Дж. Марк (1994), "Вычисление подграфа триангуляции минимального веса" , Computational Geometry: Theory & Applications , 4 (1): 18–26, DOI : 10.1016 / 0925-7721 (94) 90014-0.
  • Киркпатрик, Дэвид Г. (1980), «Заметка о Делоне и оптимальных триангуляциях», Письма об обработке информации , 10 (3): 127–128, DOI : 10.1016 / 0020-0190 (80) 90062-9 , MR  0566856.
  • Klincsek, GT (1980), "Минимальные триангуляции многоугольных областей", Анналы дискретной математики , 9 : 121-123, DOI : 10.1016 / s0167-5060 (08) 70044-х , ISBN 9780444861115.
  • Кнауэр, Кристиан; Спилнер, Андреас (2006), "Алгоритм с фиксированными параметрами для задачи триангуляции минимального веса, основанный на малых разделителях графов", Теоретико- графические концепции в информатике , Lecture Notes in Computer Science, 4271 , Berlin: Springer, pp. 49– 57, DOI : 10.1007 / 11917496_5 , МР  2290717.
  • Киода, Йошиаки; Имаи, Кейко; Такеучи, Фумихико; Таджима, Акира (1997), « Метод ветвей и разрезов для триангуляции с минимальным весом», Алгоритмы и вычисления (Сингапур, 1997) , Лекционные заметки по компьютерным наукам, 1350 , Берлин: Springer, стр. 384–393, doi : 10.1007 / 3-540-63890-3_41 , Руководство по ремонту  1651067.
  • Ленхарт, Уильям; Лиотта, Джузеппе (2002), "Проблема вытяжки для минимального веса триангуляции", Теоретическая информатика , 270 (1-2): 261-286, DOI : 10.1016 / S0304-3975 (00) 00383-2 , MR  1871072.
  • Левкопулос, Христос (1987), « Нижняя граница Ω (√ n ) для неоптимальности жадной триангуляции», Письма об обработке информации , 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) , Journal of Algorithms , 27 (2): 303–338, doi : 10.1006 / jagm.1997.0918 , MR  1622398.
  • Лингас, Анджей (1986), «Жадные триангуляции и Триангуляции Делоне неплохи в среднем», Письма об обработке информации , 22 (1): 25–31, DOI : 10.1016 / 0020-0190 (86) 90038-4.
  • Лингамы Анджей (1987), "Новый эвристический для минимального веса триангуляции", SIAM журнал на алгебраических и дискретных методов , 8 (4): 646-658, DOI : 10,1137 / 0608053 , МР  0918066.
  • Лингас, Анджей (1998), "Субэкспоненциальные алгоритмы для триангуляций с минимальным весом и связанных проблем", Труды 10-й Канадской конференции по вычислительной геометрии (CCCG'98).
  • Ллойд, Э. (1977), "О триангуляции множества точек на плоскости", Proc. 18-й симпозиум IEEE по основам информатики , стр. 228–240..
  • Manacher, Glenn K .; Зобрист, Альберт Л. (1979), «Ни жадная, ни триангуляция Делоне плоского набора точек не приближает оптимальную триангуляцию», Информационные письма , 9 (1): 31–34, DOI : 10.1016 / 0020-0190 (79 ) 90104-2 , Руководство по эксплуатации  0537055.
  • Мейер, Хенк; Раппапорт, Дэвид (1992), «Вычисление триангуляции с минимальным весом для набора линейно упорядоченных точек», Письма об обработке информации , 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.
  • Плейстед, ДА; Хонг, J. (1987), "Эвристический алгоритм триангуляции", журнал алгоритмов , 8 (3): 405-437, DOI : 10,1016 / 0196-6774 (87) 90020-4.
  • Цинь, Кайхуай; Ван, Вэньпин; Гонг, Minglun (1997), "Генетический алгоритм для минимального веса триангуляции", IEEE Международной конференция по эволюционным вычислениям ., Стр 541-546, DOI : 10,1109 / ICEC.1997.592370 , ЛВП : 10722/45578 , Семантические ученых.
  • Реми, Ян; Стегер, Анжелика (2009), «Схема аппроксимации квазиполиномиального времени для триангуляции с минимальным весом», Журнал ACM , 56 (3), статья A15, doi : 10.1145 / 1516512.1516517.
  • Шамос, Мичиган ; Hoey, DJ (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), "Алгоритм цепной декомпозиции для доказательства свойства триангуляции минимального веса", в Du, Ding-Zhu; Чжан, Сян-Сун (ред.), Алгоритмы и вычисления: 5-й Международный симпозиум, ISAAC '94, Пекин, Китайская Народная Республика, 25–27 августа 1994 г., Труды , Лекционные заметки по информатике, 834 , Берлин: Springer, стр. 423-427, DOI : 10.1007 / 3-540-58325-4_207 , МР  1316441.

Внешние ссылки [ править ]

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