Расстояние переворота

Расстояние переворота в триангуляциях

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

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

Определение

Графы переворота пятиугольника и шестиугольника

Если задано семейство триангуляций некоторого геометрического объекта, то переворот — это операция, которая преобразует одну триангуляцию в другую путем удаления ребра между двумя треугольниками и добавления противоположной диагонали к полученному четырехугольнику. Расстояние переворота между двумя триангуляциями — это минимальное количество переворотов, необходимых для преобразования одной триангуляции в другую. [1] Его также можно описать как кратчайшее расстояние пути в графе переворотов , графе, имеющем вершину для каждой триангуляции и ребро для каждого переворота между двумя триангуляциями. [1] Перевороты и расстояния переворотов можно определить таким образом для нескольких различных видов триангуляций, включая триангуляции наборов точек на евклидовой плоскости , триангуляции многоугольников и триангуляции абстрактных многообразий . [2]

Осуществимость

Расстояние переворота хорошо определено только в том случае, если любая триангуляция может быть преобразована в любую другую триангуляцию посредством последовательности переворотов. Эквивалентным условием является то, что граф переворота должен быть связным. [3]

В 1936 году Клаус Вагнер показал, что максимальные планарные графы на сфере могут быть преобразованы в любой другой максимальный планарный граф с теми же вершинами посредством переворачивания. [4] А. К. Дьюдни обобщил этот результат на триангуляции на поверхности тора , а Чарльз Лоусон — на триангуляции множества точек на двумерной плоскости. [2] [5]

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

Диаметр флип-графа

Максимальное число переворотов, необходимое для преобразования одной триангуляции в другую, равно диаметру переворотного графа. Диаметр переворотного графа выпуклого -угольника был получен Дэниелом Слейтором, Робертом Тарьяном и Уильямом Терстоном [8] при достаточно большом и Лайонелом Пурнином для всех . Этот диаметр равен , когда . [9] н {\displaystyle n} н {\displaystyle n} н {\displaystyle n} 2 н 10 {\displaystyle 2n-10} н 13 {\displaystyle n\geq 13}

Диаметр других флип-графов был изучен. Например, Клаус Вагнер предоставил квадратичную верхнюю границу диаметра флип-графа набора неотмеченных точек на сфере. [4] Текущая верхняя граница диаметра составляет , [10] в то время как наиболее известная нижняя граница составляет . [11] Диаметр флип-графов произвольных топологических поверхностей с границей также был изучен, и их точное значение известно в нескольких случаях. [12] [13] [14] н {\displaystyle n} 5 н 23 {\displaystyle 5n-23} 7 н / 3 + Θ ( 1 ) {\displaystyle 7n/3+\Тета (1)}

Эквивалентность с другими проблемами

Расстояние переворота между триангуляциями выпуклого многоугольника эквивалентно расстоянию поворота между двумя бинарными деревьями. [8]

Сложность вычислений

Нерешенная проблема в информатике :
Какова сложность вычисления расстояния переворота между двумя триангуляциями выпуклого многоугольника?

Вычисление расстояния переворота между триангуляциями множества точек является как NP-полной , так и APX-трудной задачей . [15] [16] Однако это задача с фиксированными параметрами (FPT), и было предложено несколько алгоритмов FPT, которые работают за экспоненциальное время. [17] [18]

Вычисление расстояния переворота между триангуляциями простого многоугольника также является NP-трудной задачей. [19]

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

Алгоритмы

Пусть n будет числом точек в наборе точек, а k — расстоянием переворота. Текущий лучший алгоритм FPT работает за . [17] Более быстрый алгоритм FPT существует для расстояния переворота между выпуклыми многоугольными триангуляциями; он имеет временную сложность [20] О ( н + к 32 к ) {\displaystyle O(n+k\cdot 32^{k})} О ( 3.82 к ) {\displaystyle O(3,82^{k})}

Если никакие пять точек множества точек не образуют пустой пятиугольник, то существует алгоритм для определения расстояния переворота между триангуляциями этого множества точек. [1] О ( н 2 ) {\displaystyle O(n^{2})}

Смотрите также

Ссылки

  1. ^ abc Эппштейн, Дэвид (2010). «Счастливые концовки для флип-графов». Журнал вычислительной геометрии . 1 (1): Том 1 № 1 (2010). doi :10.20382/JOCG.V1I1A2.
  2. ^ ab Dewdney, AK (1973). "Теорема Вагнера для графов тора". Дискретная математика . 4 (2). Elsevier BV: 139– 149. doi : 10.1016/0012-365x(73)90076-9 . ISSN  0012-365X.
  3. ^ ab Santos, Francisco (2005-04-02). "Несвязные торические схемы Гильберта". Mathematische Annalen . 332 (3). Springer Science and Business Media LLC: 645– 665. arXiv : math/0204044 . doi :10.1007/s00208-005-0643-5. ISSN  0025-5831.
  4. ^ аб Вагнер, К. (1936). «Bemerkungen zum Vierfarbenproblem». Jahresbericht der Deutschen Mathematiker-Vereinigung . 46 : 26–32 . ISSN  0012-0456.
  5. ^ Лоусон, Чарльз Л. (1972). «Преобразование триангуляции». Дискретная математика . 3 (4). Elsevier BV: 365– 372. doi :10.1016/0012-365x(72)90093-3. ISSN  0012-365X.
  6. ^ Сантос, Франциско (2000). «Точечный набор, пространство триангуляций которого несвязно». Журнал Американского математического общества . 13 (3). Американское математическое общество: 611– 637. doi : 10.1090/S0894-0347-00-00330-1 . hdl : 10902/2584 . ISSN  0894-0347. JSTOR  2646121.
  7. ^ Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. Т. 25. Springer.
  8. ^ ab Sleator, Daniel D.; Tarjan, Robert E .; Thurston, William P. (1988). «Расстояние вращения, триангуляции и гиперболическая геометрия». Журнал Американского математического общества . 1 (3). Американское математическое общество (AMS): 647– 681. doi : 10.1090/s0894-0347-1988-0928904-4 . ISSN  0894-0347.
  9. ^ Pournin, Lionel (2014), «Диаметр ассоциэдров», Advances in Mathematics , 259 : 13–42 , arXiv : 1207.6296 , doi : 10.1016/j.aim.2014.02.035 , MR  3197650
  10. ^ Кардинал, Жан; Хоффманн, Михаэль; Кустерс, Винсент; Тот, Чаба Д.; Веттштейн, Мануэль (2018). «Диаграммы дуг, расстояния переворота и гамильтоновы триангуляции». Computational Geometry . 68 : 206–225 . arXiv : 1611.02541 . doi : 10.1016/j.comgeo.2017.06.001 .
  11. ^ Фрати, Фабрицио (2017). «Нижняя граница диаметра флип-графа». Электронный журнал комбинаторики . 24 (1): P1.43. arXiv : 1508.03473 . doi : 10.37236/5489 .
  12. ^ Парлье, Хьюго; Пурнин, Лионель (2017). «Пространства модулей флип-графов заполняющих поверхностей». Журнал Европейского математического общества . 19 (9): 2697–2737 . arXiv : 1407.1516 . doi : 10.4171/JEMS/726 .
  13. ^ Парлье, Хьюго; Пурнин, Лионель (2018). «Модулярные флип-графы поверхностей с одним отверстием». Европейский журнал комбинаторики . 67 : 158–173 . arXiv : 1510.07664 . doi : 10.1016/j.ejc.2017.07.003 .
  14. ^ Парлье, Хьюго; Пурнин, Лионель (2018). «Однажды проколотые диски, невыпуклые многоугольники и пуантиэдры». Annals of Combinatorics . 22 (3): 619– 640. arXiv : 1602.04576 . doi : 10.1007/s00026-018-0393-1.
  15. ^ Lubiw, Anna; Pathak, Vinayak (2015). «Расстояние переворота между двумя триангуляциями множества точек является NP-полным». Computational Geometry . 49. Elsevier BV: 17– 23. arXiv : 1205.2425 . doi : 10.1016/j.comgeo.2014.11.001 . ISSN  0925-7721.
  16. ^ Pilz, Alexander (2014). «Расстояние переворота между триангуляциями плоского набора точек является APX-трудным». Computational Geometry . 47 (5). Elsevier BV: 589– 604. arXiv : 1206.3179 . doi : 10.1016/j.comgeo.2014.01.001 . ISSN  0925-7721.
  17. ^ ab Feng, Qilong; Li, Shaohua; Meng, Xiangzhong; Wang, Jianxin (2021). "Алгоритм fpt2 FPT для задачи расстояния переворота". Информация и вычисления . 281. Elsevier BV: 104708. arXiv : 1910.06185 . doi : 10.1016/j.ic.2021.104708. ISSN  0890-5401.
  18. ^ Кандж, Ияд; Седжвик, Эрик; Ся, Ге (2017-02-10). «Вычисление расстояния переворота между триангуляциями». Дискретная и вычислительная геометрия . 58 (2). Springer Science and Business Media LLC: 313– 344. arXiv : 1407.1525 . doi : 10.1007/s00454-017-9867-x. ISSN  0179-5376.
  19. ^ Айххольцер, Освин; Мульцер, Вольфганг; Пильц, Александр (2015-06-11). «Расстояние между переворотами триангуляции простого многоугольника является NP-полным». Дискретная и вычислительная геометрия . 54 (2). Springer Science and Business Media LLC: 368– 389. arXiv : 1209.0579 . doi : 10.1007/s00454-015-9709-7. ISSN  0179-5376.
  20. ^ Аб Ли, Хаохун; Ся, Гэ (2023). «Алгоритм FPT по времени 𝒪(3,82^k) для расстояния выпуклого переворота». Замок Дагштуль - Лейбниц-Центр информатики : 44:1–44:14. дои : 10.4230/LIPICS.STACS.2023.44 . Проверено 8 ноября 2023 г.
Взято с "https://en.wikipedia.org/w/index.php?title=Flip_distance&oldid=1257070312"