Полигонализация

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

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

Определение

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

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

Существование

Стейнхаус (1964) заметил, что каждое конечное множество точек, в строке которых нет трех, образует вершины простого многоугольника. ^[10] Однако требование, чтобы не было трех человек в очереди, является излишне строгим. Вместо этого все, что требуется для существования полигонализации (допускающей углы 180 °), - это то, чтобы все точки не лежали на одной линии. Если нет, то у них есть полигонализация, которую можно построить за полиномиальное время . Один из способов построения полигонализации — выбрать любую точку $q$ в выпуклой оболочке $P$ (не обязательно один из заданных пунктов). Затем радиально упорядочиваем точки вокруг $q$ (разрыв связей по расстоянию от q) производит циклическое упорядочение звездообразного многоугольника через все заданные точки с $q$ в его ядре. ^[7] Та же идея сортировки точек радиально вокруг центральной точки используется в некоторых версиях алгоритма выпуклой оболочки сканирования Грэма и может быть реализована в $O(n\log n)$ время. ^[11] Полигонализации, избегающие углов 180 °, не всегда существуют. Например, для 3×3 и 5×5 все полигонализации используют углы 180°. квадратных сеток ^[9]

Как и в случае звездообразной полигонализации, каждый неколлинеарный набор точек имеет полигонализацию, которая представляет собой монотонный многоугольник . Это означает, что относительно некоторой прямой (которую можно принять за $x$ -ось) каждая линия, перпендикулярная опорной линии, пересекает многоугольник в одном интервале или не пересекает его вообще. Конструкция Грюнбаума (1994) начинается с сортировки точек по их $x$ -координаты и проводим линию через две крайние точки. Поскольку не все точки лежат на прямой, по крайней мере одна из двух открытых полуплоскостей, ограниченных этой прямой, должна быть непустой. Грюнбаум образует две монотонные ломаные цепи, соединяющие крайние точки через отсортированные подпоследовательности точек: одну для точек этой непустой открытой полуплоскости, а другую для остальных точек. Их объединение и есть искомый монотонный многоугольник. После этапа сортировки остальная часть построения может быть выполнена за линейное время . ^[4]

NP -полно определить, имеет ли набор точек полигонализацию с использованием только ребер, параллельных осям. ^[12] Однако полигонализации с дополнительным ограничением, заключающимся в том, что они поворачивают направо в каждой вершине, если они существуют, определяются однозначно. Каждая линия, параллельная оси, проходящая через точку, должна проходить через четное число точек, и эта полигонализация должна соединять чередующиеся пары точек на этой линии. Полигонализация может быть найдена во времени $O(n\log n)$ группируя точки по одинаковым координатам и сортируя каждую группу по другой координате. ^[13] Для любого набора точек не более одного вращения может иметь полигонализацию этой формы, и это вращение снова можно найти за полиномиальное время. ^[14]

Оптимизация

Нерешенная задача по математике :

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

(еще нерешенные задачи по математике)

Проблемы поиска оптимальной полигонализации (для различных критериев оптимальности) часто вычислительно невыполнимы. Например, решение задачи о коммивояжере для данных точек не имеет пересечений. Следовательно, это всегда полигонализация, полигонализация с минимальным периметром . ^[15] Это NP-трудно найти. Точно так же известно, что найти простую полигонализацию с минимальной или максимальной площадью NP-трудно. ^[3] и был предметом некоторых вычислительных усилий. ^[16]^[17] Максимальная площадь всегда больше половины площади выпуклой оболочки , что дает коэффициент аппроксимации 2. ^[18] Точная сложность простой полигонализации с максимальным периметром и существование постоянного коэффициента аппроксимации для этой задачи остаются неизвестными. ^[5] Полигонализацию, которая минимизирует длину ее самого длинного ребра, также трудно найти с помощью NP, и ее трудно приблизить к коэффициенту аппроксимации лучше, чем ${\sqrt {3}}$ ; аппроксимация с постоянным коэффициентом неизвестна. ^[19]

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

Кратчайший битонный обход (монотонный многоугольник минимального периметра через заданные точки) всегда является полигонализацией и может быть найден за полиномиальное время. ^[22]

Подсчет

Нерешенная задача по математике :

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

(еще нерешенные задачи по математике)

Проблема подсчета всех полигонализаций заданного множества точек принадлежит #P , классу задач подсчета, связанных с проблемами решения в NP . Однако неизвестно, является ли он #P-полным , а если нет, то какова может быть его вычислительная сложность. ^[23]^[24] Множество точек имеет ровно одну полигонализацию тогда и только тогда, когда оно находится в выпуклом положении . ^[1] Существуют наборы $n$ точки, для которых число полигонализации столь же велико, как $4.64^{n}$ , ^[25] и каждый набор $n$ очков имеет не более $54.6^{n}$ полигонализации. ^[6]

Методы, применяющие теорему о плоском сепараторе к помеченным триангуляциям точек, можно использовать для подсчета всех полигонализации набора точек. $n$ точки в субэкспоненциальном времени, $n^{O({\sqrt {n}})}$ . ^[26] Динамическое программирование можно использовать для подсчета всех монотонных полигонализации за полиномиальное время, а результаты этих вычислений затем можно использовать для генерации случайной монотонной полигонализации. ^[27]

Поколение

Нерешенная задача по математике :

Могут ли локальные перемещения соединить пространство состояний полигонализации для каждого набора точек?

(еще нерешенные задачи по математике)

Неизвестно, возможно ли, чтобы система всех полигонализации образовала связное пространство состояний при локальных движениях, изменяющих ограниченное число ребер полигонализации. Если бы это было возможно, его можно было бы использовать как часть алгоритма генерации всех полигонализации путем применения обхода графа к пространству состояний. Для этой задачи недостаточно рассматривать флипы , которые удаляют два ребра полигонализации и заменяют их двумя другими ребрами, или VE-флипы , которые удаляют три ребра, два из которых имеют общую вершину, и заменяют их тремя другими ребрами. Существуют полигонализации, для которых невозможно переворот или VE-переворот, даже если в том же наборе точек есть другие полигонализации. ^[28]

Полигональные обертки — слабо простые многоугольники, которые используют каждую данную точку один или несколько раз в качестве вершины, включают в себя все полигонализации и соединяются локальными перемещениями. ^[2] Другой, более общий класс многоугольников, окружающие многоугольники , представляют собой простые многоугольники, которые имеют некоторые из заданных точек в качестве вершин и заключают в себе все точки. Они снова локально связаны и могут быть перечислены за полиномиальное время для каждого полигона. Алгоритм строит дерево многоугольников, в котором выпуклая оболочка является его корнем, а родительский элемент каждого окружающего многоугольника получается путем удаления одной вершины (что оказалось возможным путем применения теоремы о двух ушках к внешней части многоугольника). Затем к этому дереву применяется алгоритм обратного поиска для составления списка полигонов. Как следствие этого метода, все полигонализации могут быть перечислены в экспоненциальном времени ( $2^{O(n)}$ для $n$ точки) и полиномиальное пространство . ^[29]

Приложения

Классические головоломки «Соедини точки» включают в себя последовательное соединение точек, чтобы сформировать неожиданную форму, часто без пересечений. ^[30] Задача коммивояжера и ее варианты имеют множество приложений. ^[31] Полигонализация также находит применение при восстановлении контурных линий по разбросанным точкам данных и при отслеживании границ при анализе изображений . ^[32]

См. также

Теорема Данжуа–Рисса о множествах из бесконечного числа точек, которые можно соединить жордановой дугой.

Ссылки

^ Jump up to: ^а ^б Аркин, Эстер М .; Фекете, Шандор П.; Уртадо, Ферран ; Митчелл, Джозеф С.Б .; Нет, Марк; Сакристан, Вера; Сетия, Саураб (2003), «О рефлексивности множеств точек», Аронов, Борис ; Басу, Саугата; Пах, Янош ; Шарир, Миха (ред.), Дискретная и вычислительная геометрия: Фестиваль Гудмана-Поллака , Алгоритмы и комбинаторика, том. 25, Берлин: Springer, стр. 139–156, номер документа : 10.1007/978-3-642-55566-4_6 , ISBN. 978-3-642-62442-1 , МР 2038472
^ Jump up to: ^а ^б ^с Дамиан, Мирела; Флатленд, Робин; О'Рурк, Джозеф ; Рамасвами, Сунита (2010), «Соединение полигонизаций посредством растяжений и звуков» , Теория вычислительных систем , 47 (3): 674–695, arXiv : 0709.1942 , doi : 10.1007/s00224-009-9192-8 , MR 2652036 , S2CID 59602
^ Jump up to: ^а ^б Фекете, С.П. (2000), «О простых полигонализациях с оптимальной площадью», Дискретная и вычислительная геометрия , 23 (1): 73–110, doi : 10.1007/PL00009492 , MR 1727124 , S2CID 15835121
^ Jump up to: ^а ^б Грюнбаум, Бранко (1994), «Гамильтоновы многоугольники и многогранники» (PDF) , Geombinatorics , 3 (3): 83–89, MR 1326479
^ Jump up to: ^а ^б Думитреску, Адриан; Тот, Чаба Д. (2010), «Длинные непересекающиеся конфигурации на плоскости», Дискретная и вычислительная геометрия , 44 (4): 727–752, arXiv : 0909.4094 , doi : 10.1007/s00454-010-9277-9 , МР 2728029 , S2CID 2813190
^ Jump up to: ^а ^б Шарир, Миша ; Шеффер, Адам; Вельцль, Эмо (2013), «Считающиеся плоские графы: идеальные паросочетания, остовные циклы и техника Кастелейна», Журнал комбинаторной теории , серия A, 120 (4): 777–794, arXiv : 1109.5596 , doi : 10.1016/j. jcta.2013.01.002 , МР 3022612
^ Jump up to: ^а ^б Денин, Линда; Шут, Гэри (1988), «Полигонизация наборов точек на плоскости», Дискретная и вычислительная геометрия , 3 (1): 77–87, doi : 10.1007/BF02187898 , MR 0918181
^ Малкевич, Джозеф (2016), «Являются ли точные определения хорошей идеей?» , Рубрика статей AMS , Американское математическое общество
^ Jump up to: ^а ^б Чоу, Сэм; Гафни, Айла; Гафни, Пол (март 2021 г.), «Соединение точек: максимальные многоугольники в квадратной сетке», Mathematics Magazine , 94 (2): 118–124, doi : 10.1080/0025570x.2021.1869493 , MR 4241975 , S2CID 233185771
^ Штайнхаус, Хьюго (1964), Сто задач по элементарной математике , Basic Books, стр. 17, 85–86, ISBN 9780486811802
^ Грэм, Р.Л. (июнь 1972 г.), «Эффективный алгоритм определения выпуклой оболочки конечного плоского множества» (PDF) , Information Processing Letters , 1 (4): 132–133, doi : 10.1016/0020-0190(72) 90045-2
^ Раппапорт, Дэвид (1986), О сложности вычисления ортогональных многоугольников по набору точек , Технический отчет, том. SOCS-86.9, Монреаль: Университет Макгилла
^ О'Рурк, Джозеф (1988), «Уникальность ортогональных соединений точек», в Туссене, Годфрид Т. (ред.), Вычислительная морфология: вычислительно-геометрический подход к анализу формы , машинному интеллекту и распознаванию образов, том. 6, Амстердам: Северная Голландия, стр. 97–104, doi : 10.1016/B978-0-444-70467-2.50013-8 , ISBN. 978-0-444-70467-2 , МР 0994001
^ Леффлер, Мартен; Мамфорд, Елена (2011), «Связные прямолинейные графы на множествах точек», Журнал вычислительной геометрии , 2 (1): 1–15, doi : 10.20382/v2i1a1 , MR 2786032
^ Кинтас, LV; Супник, Фред (1965), «О некоторых свойствах кратчайших гамильтоновых схем», The American Mathematical Monthly , 72 (9): 977–980, doi : 10.2307/2313333 , JSTOR 2313333 , MR 0188872
^ Демейн, Эрик Д .; Фекете, Шандор П.; Кельденич, Филипп; Крупке, Доминик; Митчелл, Джозеф С.Б. (2022), «Простые полигонализации, оптимальные по площади: задача компьютерной графики 2019», Журнал экспериментальных алгоритмов ACM , 27 : Ст. 2,4, 12, doi : 10,1145/3504000 , hdl : 1721,1/146480 , MR 4390039 , S2CID 244117500
^ Рамос, Натанаэль; де Резенде, Педро Дж.; де Соуза, Сид К. (2022), «Задачи полигонизации оптимальных областей: точные решения посредством геометрической двойственности», Computers & Operations Research , 145 , статья № 105842, doi : 10.1016/j.cor.2022.105842 , MR 4418151 , S2CID 248369389
^ Фекете, Шандор П. (1992), Геометрия и задача коммивояжера (докторская диссертация), Университет Ватерлоо, ProQuest 304035266 Для полигонализации площади, превышающей половину выпуклой оболочки, см. теорему 4.2.1, стр. 56.
^ Фекете, Шандор П.; Кельдених, Филипп (2018), «Вычисление конфигураций без пересечений с минимальным узким местом» (PDF) , 34-й Европейский семинар по вычислительной геометрии , Свободный университет Берлина, стр. 23:1–23:6
^ ван Леувен, Ян ; Шон, Аннеке А. (1981), «Распутывание путешествия коммивояжера в самолете» (PDF) , в Мюльбахере, Йорг Р. (ред.), Труды 7-й конференции «Графотеоретические концепции в компьютерных науках» (WG '81), Линц, Австрия, 15–17 июня 1981 г. , Хансер, Мюнхен, стр. 87–98, MR 0708744.
^ Энглерт, Матиас; Реглин, Хайко; Вёкинг, Бертольд (2014), «Наихудший случай и вероятностный анализ двухопционного алгоритма для TSP», Algorithmica , 68 (1): 190–264, arXiv : 2302.06889 , doi : 10.1007/s00453-013-9801-4 , МР 3147481 , S2CID 1638275
^ де Берг, Марк ; Бучин, Кевин; Янсен, член парламента от Барта; Воегингер, Герхард (2016), «Мелкозернистый анализ сложности двух классических вариантов TSP» , в Хацигианнакисе, Иоаннис; Митценмахер, Майкл ; Рабани, Юваль; Санджорджи, Давиде (ред.), 43-й Международный коллоквиум по автоматам, языкам и программированию (ICALP 2016) , Международные труды Лейбница по информатике (LIPIcs), том. 55, Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, стр. 5:1–5:14, doi : 10.4230/LIPIcs.ICALP.2016.5 , ISBN 978-3-95977-013-2
^ Митчелл, Джозеф С.Б .; О'Рурк, Джозеф (2001), «Столбец 42 по вычислительной геометрии», Международный журнал вычислительной геометрии и приложений , 11 (5): 573–582, arXiv : cs/0108021 , doi : 10.1142/S0218195901000651 , MR 1862888
^ О'Рурк, Джозеф (1 января 2003 г.), «Проблема 16: Простая полигонализация» , Проект «Открытые проблемы».
^ Гарсиа, Альфредо; Нет, Марк; Теджель, Хавьер (2000), «Нижние границы количества подграфов без пересечений $K_{N}$ ", Вычислительная геометрия: теория и приложения" , 16 (4): 211–221, doi : 10.1016/S0925-7721(00)00010-9 , MR 1775294.
^ Маркс, Даниэль; Мильцов, Тиллманн (2016), «Чищение и покусывание кактуса: алгоритмы субэкспоненциального времени для подсчета триангуляций и связанных с ними проблем», в Фекете, Шандор П.; Любив, Анна (ред.), 32-й Международный симпозиум по вычислительной геометрии, SoCG 2016, 14–18 июня 2016 г., Бостон, Массачусетс, США , LIPIcs, vol. 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 52:1–52:16, arXiv : 1603.07340 , doi : 10.4230/LIPIcs.SoCG.2016.52 , ISBN 9783959770095 , МР 3540894 , S2CID 7668194
^ Чжу, Чонг; Сундарам, Гопалакришнан; Снойинк, Джек; Митчелл, Джозеф С.Б. (1996), «Генерация случайных многоугольников с заданными вершинами», Вычислительная геометрия: теория и приложения , 6 (5): 277–290, doi : 10.1016/0925-7721(95)00031-3 , MR 1408922
^ Jump up to: ^а ^б Эрнандо, Кармен; Хоул, Майкл Э.; Уртадо, Ферран (2002), «О локальном преобразовании многоугольников со свойствами видимости», Theoretical Computer Science , 289 (2): 919–937, doi : 10.1016/S0304-3975(01)00409-1 , MR 1945256
^ Яманака, Кацухиса; Авис, Дэвид ; Хорияма, Такаши; Окамото, Ёсио; Уэхара, Рюхей; Ямаути, Танами (2021), «Алгоритмическое перечисление окружающих многоугольников» (PDF) , Дискретная прикладная математика , 303 : 305–313, doi : 10.1016/j.dam.2020.03.034 , MR 4310502
^ Леффлер, Мартен; Кайзер, Мира; ван Капель, Тим; Клаппе, Гервин; ван Кревелд, Марк Дж .; Стаалс, Франк (2014), «Семейство головоломок Connect-The-Dots: проектирование и автоматическое создание», ACM Transactions on Graphics , 33 (4): 72:1–72:10, doi : 10.1145/2601097.2601224 , S2CID 9774101
^ Кук, Уильям Дж. (2012), «Глава 3: Продавец в действии», В погоне за коммивояжером , Princeton University Press, Принстон, Нью-Джерси, стр. 44–61, ISBN 978-0-691-15270-7 , МР 2866515
^ Стеллингер, Пер (2010), «Соедините точки: реконструкция границ региона по контурным точкам выборки», в Кете, Ульрих; Монтанверт, Анник; Сойль, Пьер (ред.), Приложения дискретной геометрии и математической морфологии - Первый международный семинар, WADGMM 2010, Стамбул, Турция, 22 августа 2010 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 7346, Springer, стр. 1–13, номер документа : 10.1007/978-3-642-32313-3_1 , ISBN. 978-3-642-32312-6

[reflexivity-1] Jump up to: ^а ^б Аркин, Эстер М .; Фекете, Шандор П.; Уртадо, Ферран ; Митчелл, Джозеф С.Б .; Нет, Марк; Сакристан, Вера; Сетия, Саураб (2003), «О рефлексивности множеств точек», Аронов, Борис ; Басу, Саугата; Пах, Янош ; Шарир, Миха (ред.), Дискретная и вычислительная геометрия: Фестиваль Гудмана-Поллака , Алгоритмы и комбинаторика, том. 25, Берлин: Springer, стр. 139–156, номер документа : 10.1007/978-3-642-55566-4_6 , ISBN. 978-3-642-62442-1 , МР 2038472

[dfor-2] Jump up to: ^а ^б ^с Дамиан, Мирела; Флатленд, Робин; О'Рурк, Джозеф ; Рамасвами, Сунита (2010), «Соединение полигонизаций посредством растяжений и звуков» , Теория вычислительных систем , 47 (3): 674–695, arXiv : 0709.1942 , doi : 10.1007/s00224-009-9192-8 , MR 2652036 , S2CID 59602

[fekete-3] Jump up to: ^а ^б Фекете, С.П. (2000), «О простых полигонализациях с оптимальной площадью», Дискретная и вычислительная геометрия , 23 (1): 73–110, doi : 10.1007/PL00009492 , MR 1727124 , S2CID 15835121

[grunbaum-4] Jump up to: ^а ^б Грюнбаум, Бранко (1994), «Гамильтоновы многоугольники и многогранники» (PDF) , Geombinatorics , 3 (3): 83–89, MR 1326479

[long-5] Jump up to: ^а ^б Думитреску, Адриан; Тот, Чаба Д. (2010), «Длинные непересекающиеся конфигурации на плоскости», Дискретная и вычислительная геометрия , 44 (4): 727–752, arXiv : 0909.4094 , doi : 10.1007/s00454-010-9277-9 , МР 2728029 , S2CID 2813190

[ssw-6] Jump up to: ^а ^б Шарир, Миша ; Шеффер, Адам; Вельцль, Эмо (2013), «Считающиеся плоские графы: идеальные паросочетания, остовные циклы и техника Кастелейна», Журнал комбинаторной теории , серия A, 120 (4): 777–794, arXiv : 1109.5596 , doi : 10.1016/j. jcta.2013.01.002 , МР 3022612

[star-shaped-7] Jump up to: ^а ^б Денин, Линда; Шут, Гэри (1988), «Полигонизация наборов точек на плоскости», Дискретная и вычислительная геометрия , 3 (1): 77–87, doi : 10.1007/BF02187898 , MR 0918181

[precise-8] Малкевич, Джозеф (2016), «Являются ли точные определения хорошей идеей?» , Рубрика статей AMS , Американское математическое общество

[grid-9] Jump up to: ^а ^б Чоу, Сэм; Гафни, Айла; Гафни, Пол (март 2021 г.), «Соединение точек: максимальные многоугольники в квадратной сетке», Mathematics Magazine , 94 (2): 118–124, doi : 10.1080/0025570x.2021.1869493 , MR 4241975 , S2CID 233185771

[steinhaus-10] Штайнхаус, Хьюго (1964), Сто задач по элементарной математике , Basic Books, стр. 17, 85–86, ISBN 9780486811802

[graham-11] Грэм, Р.Л. (июнь 1972 г.), «Эффективный алгоритм определения выпуклой оболочки конечного плоского множества» (PDF) , Information Processing Letters , 1 (4): 132–133, doi : 10.1016/0020-0190(72) 90045-2

[rappaport-12] Раппапорт, Дэвид (1986), О сложности вычисления ортогональных многоугольников по набору точек , Технический отчет, том. SOCS-86.9, Монреаль: Университет Макгилла

[orthogonal-13] О'Рурк, Джозеф (1988), «Уникальность ортогональных соединений точек», в Туссене, Годфрид Т. (ред.), Вычислительная морфология: вычислительно-геометрический подход к анализу формы , машинному интеллекту и распознаванию образов, том. 6, Амстердам: Северная Голландия, стр. 97–104, doi : 10.1016/B978-0-444-70467-2.50013-8 , ISBN. 978-0-444-70467-2 , МР 0994001

[rotate-14] Леффлер, Мартен; Мамфорд, Елена (2011), «Связные прямолинейные графы на множествах точек», Журнал вычислительной геометрии , 2 (1): 1–15, doi : 10.20382/v2i1a1 , MR 2786032

[qs-15] Кинтас, LV; Супник, Фред (1965), «О некоторых свойствах кратчайших гамильтоновых схем», The American Mathematical Monthly , 72 (9): 977–980, doi : 10.2307/2313333 , JSTOR 2313333 , MR 0188872

[contest-16] Демейн, Эрик Д .; Фекете, Шандор П.; Кельденич, Филипп; Крупке, Доминик; Митчелл, Джозеф С.Б. (2022), «Простые полигонализации, оптимальные по площади: задача компьютерной графики 2019», Журнал экспериментальных алгоритмов ACM , 27 : Ст. 2,4, 12, doi : 10,1145/3504000 , hdl : 1721,1/146480 , MR 4390039 , S2CID 244117500

[area-ilp-17] Рамос, Натанаэль; де Резенде, Педро Дж.; де Соуза, Сид К. (2022), «Задачи полигонизации оптимальных областей: точные решения посредством геометрической двойственности», Computers & Operations Research , 145 , статья № 105842, doi : 10.1016/j.cor.2022.105842 , MR 4418151 , S2CID 248369389

[tsp-18] Фекете, Шандор П. (1992), Геометрия и задача коммивояжера (докторская диссертация), Университет Ватерлоо, ProQuest 304035266 Для полигонализации площади, превышающей половину выпуклой оболочки, см. теорему 4.2.1, стр. 56.

[bottleneck-19] Фекете, Шандор П.; Кельдених, Филипп (2018), «Вычисление конфигураций без пересечений с минимальным узким местом» (PDF) , 34-й Европейский семинар по вычислительной геометрии , Свободный университет Берлина, стр. 23:1–23:6

[vls-20] ван Леувен, Ян ; Шон, Аннеке А. (1981), «Распутывание путешествия коммивояжера в самолете» (PDF) , в Мюльбахере, Йорг Р. (ред.), Труды 7-й конференции «Графотеоретические концепции в компьютерных науках» (WG '81), Линц, Австрия, 15–17 июня 1981 г. , Хансер, Мюнхен, стр. 87–98, MR 0708744.

[erv-21] Энглерт, Матиас; Реглин, Хайко; Вёкинг, Бертольд (2014), «Наихудший случай и вероятностный анализ двухопционного алгоритма для TSP», Algorithmica , 68 (1): 190–264, arXiv : 2302.06889 , doi : 10.1007/s00453-013-9801-4 , МР 3147481 , S2CID 1638275

[bbjw-22] де Берг, Марк ; Бучин, Кевин; Янсен, член парламента от Барта; Воегингер, Герхард (2016), «Мелкозернистый анализ сложности двух классических вариантов TSP» , в Хацигианнакисе, Иоаннис; Митценмахер, Майкл ; Рабани, Юваль; Санджорджи, Давиде (ред.), 43-й Международный коллоквиум по автоматам, языкам и программированию (ICALP 2016) , Международные труды Лейбница по информатике (LIPIcs), том. 55, Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, стр. 5:1–5:14, doi : 10.4230/LIPIcs.ICALP.2016.5 , ISBN 978-3-95977-013-2

[cg42-23] Митчелл, Джозеф С.Б .; О'Рурк, Джозеф (2001), «Столбец 42 по вычислительной геометрии», Международный журнал вычислительной геометрии и приложений , 11 (5): 573–582, arXiv : cs/0108021 , doi : 10.1142/S0218195901000651 , MR 1862888

[topp-24] О'Рурк, Джозеф (1 января 2003 г.), «Проблема 16: Простая полигонализация» , Проект «Открытые проблемы».

[gnt-25] Гарсиа, Альфредо; Нет, Марк; Теджель, Хавьер (2000), «Нижние границы количества подграфов без пересечений $K_{N}$ ", Вычислительная геометрия: теория и приложения" , 16 (4): 211–221, doi : 10.1016/S0925-7721(00)00010-9 , MR 1775294.

[cactus-26] Маркс, Даниэль; Мильцов, Тиллманн (2016), «Чищение и покусывание кактуса: алгоритмы субэкспоненциального времени для подсчета триангуляций и связанных с ними проблем», в Фекете, Шандор П.; Любив, Анна (ред.), 32-й Международный симпозиум по вычислительной геометрии, SoCG 2016, 14–18 июня 2016 г., Бостон, Массачусетс, США , LIPIcs, vol. 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 52:1–52:16, arXiv : 1603.07340 , doi : 10.4230/LIPIcs.SoCG.2016.52 , ISBN 9783959770095 , МР 3540894 , S2CID 7668194

[zssm-27] Чжу, Чонг; Сундарам, Гопалакришнан; Снойинк, Джек; Митчелл, Джозеф С.Б. (1996), «Генерация случайных многоугольников с заданными вершинами», Вычислительная геометрия: теория и приложения , 6 (5): 277–290, doi : 10.1016/0925-7721(95)00031-3 , MR 1408922

[hhh-28] Jump up to: ^а ^б Эрнандо, Кармен; Хоул, Майкл Э.; Уртадо, Ферран (2002), «О локальном преобразовании многоугольников со свойствами видимости», Theoretical Computer Science , 289 (2): 919–937, doi : 10.1016/S0304-3975(01)00409-1 , MR 1945256

[yahouy-29] Яманака, Кацухиса; Авис, Дэвид ; Хорияма, Такаши; Окамото, Ёсио; Уэхара, Рюхей; Ямаути, Танами (2021), «Алгоритмическое перечисление окружающих многоугольников» (PDF) , Дискретная прикладная математика , 303 : 305–313, doi : 10.1016/j.dam.2020.03.034 , MR 4310502

[ctd-30] Леффлер, Мартен; Кайзер, Мира; ван Капель, Тим; Клаппе, Гервин; ван Кревелд, Марк Дж .; Стаалс, Франк (2014), «Семейство головоломок Connect-The-Dots: проектирование и автоматическое создание», ACM Transactions on Graphics , 33 (4): 72:1–72:10, doi : 10.1145/2601097.2601224 , S2CID 9774101

[pursuit-31] Кук, Уильям Дж. (2012), «Глава 3: Продавец в действии», В погоне за коммивояжером , Princeton University Press, Принстон, Нью-Джерси, стр. 44–61, ISBN 978-0-691-15270-7 , МР 2866515

[contour-32] Стеллингер, Пер (2010), «Соедините точки: реконструкция границ региона по контурным точкам выборки», в Кете, Ульрих; Монтанверт, Анник; Сойль, Пьер (ред.), Приложения дискретной геометрии и математической морфологии - Первый международный семинар, WADGMM 2010, Стамбул, Турция, 22 августа 2010 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 7346, Springer, стр. 1–13, номер документа : 10.1007/978-3-642-32313-3_1 , ISBN. 978-3-642-32312-6

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]