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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

Вычислительная сложность

Нерешенная проблема в информатике :

Какова сложность вычисления расстояния переворачивания между двумя треугольниками выпуклого многоугольника?

(Более нерешенные проблемы в информатике)

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

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

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

Алгоритмы

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

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

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с Эппштейн, Дэвид (2010). «Счастливый конец для флип-графов» . Журнал вычислительной геометрии . 1 (1): Том. 1 № 1 (2010). дои : 10.20382/JOCG.V1I1A2 .
^ Перейти обратно: ^а ^б Дьюдни, АК (1973). «Теорема Вагнера для графов тора» . Дискретная математика . 4 (2). Эльзевир Б.В.: 139–149. дои : 10.1016/0012-365x(73)90076-9 . ISSN 0012-365X .
^ Перейти обратно: ^а ^б Сантос, Франциско (2 апреля 2005 г.). «Несвязные торические схемы Гильберта». Математические Аннален . 332 (3). ООО «Спрингер Сайенс энд Бизнес Медиа»: 645–665. arXiv : математика/0204044 . дои : 10.1007/s00208-005-0643-5 . ISSN 0025-5831 .
^ Перейти обратно: ^а ^б Вагнер, К. (1936). «Замечания о задаче четырёх красок» . Годовой отчет Немецкой ассоциации математиков . 46 :26-32. ISSN 0012-0456 .
^ Лоусон, Чарльз Л. (1972). «Преобразование триангуляций». Дискретная математика . 3 (4). Эльзевир Б.В.: 365–372. дои : 10.1016/0012-365x(72)90093-3 . ISSN 0012-365X .
^ Сантос, Франциско (2000). «Множество точек, пространство триангуляций которого несвязно» . Журнал Американского математического общества . 13 (3). Американское математическое общество: 611–637. дои : 10.1090/S0894-0347-00-00330-1 . hdl : 10902/2584 . ISSN 0894-0347 . JSTOR 2646121 .
^ Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. Том. 25. Спрингер.
^ Перейти обратно: ^а ^б Слитор, Дэниел Д.; Тарьян, Роберт Э .; Терстон, Уильям П. (1988). «Расстояние вращения, триангуляции и гиперболическая геометрия» . Журнал Американского математического общества . 1 (3). Американское математическое общество (AMS): 647–681. дои : 10.1090/s0894-0347-1988-0928904-4 . ISSN 0894-0347 .
^ Пурнен, Лайонел (2014), «Диаметр ассоциэдров», Успехи в математике , 259 : 13–42, arXiv : 1207.6296 , doi : 10.1016/j.aim.2014.02.035 , MR 3197650
^ Бозе, Просенджит; Вердоншот, Сандер (2012). «История флипов в комбинаторных триангуляциях». Конспекты лекций по информатике . Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 29–44. arXiv : 1206.0303 . дои : 10.1007/978-3-642-34191-5_3 . ISBN 978-3-642-34190-8 . ISSN 0302-9743 . S2CID 18896454 .
^ Фрати, Фабрицио (2017). «Нижняя граница диаметра флип-графа» . Электронный журнал комбинаторики . 24 (1): P1.43. arXiv : 1508.03473 . дои : 10.37236/5489 .
^ Парлье, Хьюго; Пурнен, Лайонел (2017). «Пространства модулей флип-графов заполняющих поверхностей» . Журнал Европейского математического общества . 19 (9): 2697–2737. arXiv : 1407.1516 . дои : 10.4171/JEMS/726 .
^ Парлье, Хьюго; Пурнен, Лайонел (2018). «Модульные флип-графы однодырочных поверхностей» . Европейский журнал комбинаторики . 67 : 158–173. arXiv : 1510.07664 . дои : 10.1016/j.ejc.2017.07.003 .
^ Парлье, Хьюго; Пурнен, Лайонел (2018). «Однажды проколотые диски, невыпуклые многоугольники и остроконечники». Анналы комбинаторики . 22 (3): 619–640. arXiv : 1602.04576 . дои : 10.1007/s00026-018-0393-1 .
^ Любив, Анна; Патхак, Винаяк (2015). «Расстояние переворота между двумя триангуляциями набора точек NP-полное» . Вычислительная геометрия . 49 . Эльзевир Б.В.: 17–23. arXiv : 1205.2425 . дои : 10.1016/j.comgeo.2014.11.001 . ISSN 0925-7721 .
^ Пильц, Александр (2014). «Расстояние переворота между триангуляциями плоского набора точек является APX-сложным» . Вычислительная геометрия . 47 (5). Эльзевир Б.В.: 589–604. arXiv : 1206.3179 . дои : 10.1016/j.comgeo.2014.01.001 . ISSN 0925-7721 .
^ Перейти обратно: ^а ^б Фэн, Цилун; Ли, Шаохуа; Мэн, Сянчжун; Ван, Цзяньсинь (2021). «Алгоритм fpt2 FPT для задачи переворота расстояния». Информация и вычисления . 281 . Эльзевир Б.В.: 104708. arXiv : 1910.06185 . дои : 10.1016/j.ic.2021.104708 . ISSN 0890-5401 .
^ Кандж, Ияд; Седжвик, Эрик; Ся, Гэ (10 февраля 2017 г.). «Вычисление перевернутого расстояния между триангуляциями». Дискретная и вычислительная геометрия . 58 (2). ООО «Спрингер Сайенс энд Бизнес Медиа»: 313–344. arXiv : 1407.1525 . дои : 10.1007/s00454-017-9867-x . ISSN 0179-5376 .
^ Айххольцер, Освин; Мюльцер, Вольфганг; Пильц, Александр (11 июня 2015 г.). «Обратное расстояние между триангуляциями простого многоугольника является NP-полным». Дискретная и вычислительная геометрия . 54 (2). ООО «Спрингер Сайенс энд Бизнес Медиа»: 368–389. arXiv : 1209.0579 . дои : 10.1007/s00454-015-9709-7 . ISSN 0179-5376 .
^ Перейти обратно: ^а ^б Ли, Хаохун; Ся, Гэ (2023). «Алгоритм FPT по времени 𝒪(3,82^k) для расстояния выпуклого переворота» . Замок Дагштуль — Центр информатики Лейбница . дои : 10.4230/LIPICS.STACS.2023.44 . Проверено 8 ноября 2023 г.

[eppstein-1] Перейти обратно: ^а ^б ^с Эппштейн, Дэвид (2010). «Счастливый конец для флип-графов» . Журнал вычислительной геометрии . 1 (1): Том. 1 № 1 (2010). дои : 10.20382/JOCG.V1I1A2 .

[dewdney-2] Перейти обратно: ^а ^б Дьюдни, АК (1973). «Теорема Вагнера для графов тора» . Дискретная математика . 4 (2). Эльзевир Б.В.: 139–149. дои : 10.1016/0012-365x(73)90076-9 . ISSN 0012-365X .

[santos2-3] Перейти обратно: ^а ^б Сантос, Франциско (2 апреля 2005 г.). «Несвязные торические схемы Гильберта». Математические Аннален . 332 (3). ООО «Спрингер Сайенс энд Бизнес Медиа»: 645–665. arXiv : математика/0204044 . дои : 10.1007/s00208-005-0643-5 . ISSN 0025-5831 .

[wagner-4] Перейти обратно: ^а ^б Вагнер, К. (1936). «Замечания о задаче четырёх красок» . Годовой отчет Немецкой ассоциации математиков . 46 :26-32. ISSN 0012-0456 .

[lawson-5] Лоусон, Чарльз Л. (1972). «Преобразование триангуляций». Дискретная математика . 3 (4). Эльзевир Б.В.: 365–372. дои : 10.1016/0012-365x(72)90093-3 . ISSN 0012-365X .

[santos-6] Сантос, Франциско (2000). «Множество точек, пространство триангуляций которого несвязно» . Журнал Американского математического общества . 13 (3). Американское математическое общество: 611–637. дои : 10.1090/S0894-0347-00-00330-1 . hdl : 10902/2584 . ISSN 0894-0347 . JSTOR 2646121 .

[loera-7] Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. Том. 25. Спрингер.

[stt-8] Перейти обратно: ^а ^б Слитор, Дэниел Д.; Тарьян, Роберт Э .; Терстон, Уильям П. (1988). «Расстояние вращения, триангуляции и гиперболическая геометрия» . Журнал Американского математического общества . 1 (3). Американское математическое общество (AMS): 647–681. дои : 10.1090/s0894-0347-1988-0928904-4 . ISSN 0894-0347 .

[pournin-9] Пурнен, Лайонел (2014), «Диаметр ассоциэдров», Успехи в математике , 259 : 13–42, arXiv : 1207.6296 , doi : 10.1016/j.aim.2014.02.035 , MR 3197650

[bv-10] Бозе, Просенджит; Вердоншот, Сандер (2012). «История флипов в комбинаторных триангуляциях». Конспекты лекций по информатике . Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 29–44. arXiv : 1206.0303 . дои : 10.1007/978-3-642-34191-5_3 . ISBN 978-3-642-34190-8 . ISSN 0302-9743 . S2CID 18896454 .

[frati-11] Фрати, Фабрицио (2017). «Нижняя граница диаметра флип-графа» . Электронный журнал комбинаторики . 24 (1): P1.43. arXiv : 1508.03473 . дои : 10.37236/5489 .

[pp2017-12] Парлье, Хьюго; Пурнен, Лайонел (2017). «Пространства модулей флип-графов заполняющих поверхностей» . Журнал Европейского математического общества . 19 (9): 2697–2737. arXiv : 1407.1516 . дои : 10.4171/JEMS/726 .

[pp2018a-13] Парлье, Хьюго; Пурнен, Лайонел (2018). «Модульные флип-графы однодырочных поверхностей» . Европейский журнал комбинаторики . 67 : 158–173. arXiv : 1510.07664 . дои : 10.1016/j.ejc.2017.07.003 .

[pp2018b-14] Парлье, Хьюго; Пурнен, Лайонел (2018). «Однажды проколотые диски, невыпуклые многоугольники и остроконечники». Анналы комбинаторики . 22 (3): 619–640. arXiv : 1602.04576 . дои : 10.1007/s00026-018-0393-1 .

[lp-15] Любив, Анна; Патхак, Винаяк (2015). «Расстояние переворота между двумя триангуляциями набора точек NP-полное» . Вычислительная геометрия . 49 . Эльзевир Б.В.: 17–23. arXiv : 1205.2425 . дои : 10.1016/j.comgeo.2014.11.001 . ISSN 0925-7721 .

[pilz-16] Пильц, Александр (2014). «Расстояние переворота между триангуляциями плоского набора точек является APX-сложным» . Вычислительная геометрия . 47 (5). Эльзевир Б.В.: 589–604. arXiv : 1206.3179 . дои : 10.1016/j.comgeo.2014.01.001 . ISSN 0925-7721 .

[fpt2-17] Перейти обратно: ^а ^б Фэн, Цилун; Ли, Шаохуа; Мэн, Сянчжун; Ван, Цзяньсинь (2021). «Алгоритм fpt2 FPT для задачи переворота расстояния». Информация и вычисления . 281 . Эльзевир Б.В.: 104708. arXiv : 1910.06185 . дои : 10.1016/j.ic.2021.104708 . ISSN 0890-5401 .

[fpt1-18] Кандж, Ияд; Седжвик, Эрик; Ся, Гэ (10 февраля 2017 г.). «Вычисление перевернутого расстояния между триангуляциями». Дискретная и вычислительная геометрия . 58 (2). ООО «Спрингер Сайенс энд Бизнес Медиа»: 313–344. arXiv : 1407.1525 . дои : 10.1007/s00454-017-9867-x . ISSN 0179-5376 .

[amp-19] Айххольцер, Освин; Мюльцер, Вольфганг; Пильц, Александр (11 июня 2015 г.). «Обратное расстояние между триангуляциями простого многоугольника является NP-полным». Дискретная и вычислительная геометрия . 54 (2). ООО «Спрингер Сайенс энд Бизнес Медиа»: 368–389. arXiv : 1209.0579 . дои : 10.1007/s00454-015-9709-7 . ISSN 0179-5376 .

[fpt-convex-20] Перейти обратно: ^а ^б Ли, Хаохун; Ся, Гэ (2023). «Алгоритм FPT по времени 𝒪(3,82^k) для расстояния выпуклого переворота» . Замок Дагштуль — Центр информатики Лейбница . дои : 10.4230/LIPICS.STACS.2023.44 . Проверено 8 ноября 2023 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]