Простой многоугольник

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

Сумма внешних углов простого многоугольника равна $2\pi$ . Каждый простой многоугольник с $n$ можно триангулировать стороны $n-3$ его диагоналей, и по теореме о художественной галерее его внутренняя часть видна с некоторых $\lfloor n/3\rfloor$ его вершин.

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

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

Определения [ править ]

Простой многоугольник — это замкнутая кривая на евклидовой плоскости, состоящая из отрезков прямых , соединяющихся друг с другом, образующих многоугольную цепь . ^[1] Два отрезка линии встречаются в каждой конечной точке, и между отрезками линии нет других точек пересечения. Никакое подходящее подмножество отрезков прямой не имеет таких свойств. ^[2] Квалификатор simple иногда опускается, при этом предполагается, что слово многоугольник означает простой многоугольник. ^[3]

Отрезки линий, образующие многоугольник, называются его краями или сторонами . Конечная точка сегмента называется вершиной ( множественное число: вершины). ^[2] или угол . Ребра и вершины более формальны, но могут быть неоднозначными в контекстах, которые также включают ребра и вершины графа ; более разговорные термины стороны и углы . Чтобы избежать этой двусмысленности, можно использовать ^[4] Количество ребер всегда равно количеству вершин. ^[2] Некоторые источники допускают, чтобы два отрезка линии образовывали прямой угол (180 °), ^[5] в то время как другие запрещают это, вместо этого требуя, чтобы коллинеарные сегменты замкнутой многоугольной цепи были объединены в одну более длинную сторону. ^[6] Две вершины являются соседями , если они являются двумя концами одной из сторон многоугольника. ^[7]

Простые многоугольники иногда называют жордановыми многоугольниками , потому что они являются жордановыми кривыми ; Теорему Жордана о кривой можно использовать, чтобы доказать, что такой многоугольник делит плоскость на две области. ^[8] Действительно, первоначальное доказательство этой теоремы Камиллы Жордан в качестве отправной точки взяло частный случай простых многоугольников (указанный без доказательства). ^[9] Область внутри многоугольника (его внутренность ) образует ограниченное множество ^[2] топологически эквивалентен открытому диску по теореме Жордана – Шёнфлиса , ^[10] с конечной, но ненулевой площадью . ^[11] Сам многоугольник топологически эквивалентен кругу , ^[12] а область снаружи ( внешняя ) представляет собой неограниченное связное открытое множество с бесконечной площадью. ^[11] Хотя формальное определение простого многоугольника обычно представляет собой систему отрезков прямых, также возможно (и часто встречается в неформальном использовании) определить простой многоугольник как замкнутое множество на плоскости, объединение этих отрезков с внутренней частью. многоугольника. ^[2]

Диагональю простого многоугольника является любой отрезок линии, который имеет две вершины многоугольника в качестве своих конечных точек и который в противном случае полностью находится внутри многоугольника. ^[13]

Свойства [ править ]

Внутренний угол простого многоугольника в одной из его вершин — это угол, охватываемый внутренней частью многоугольника в этой вершине. Вершина называется выпуклой, если ее внутренний угол меньше $\pi$ (прямой угол 180°) и вогнутый , если внутренний угол больше $\pi$ . Если внутренний угол $\theta$ , внешний угол при той же вершине определяется как его дополнение $\pi -\theta$ , угол поворота от одной направленной стороны к другой. Внешний угол положителен в выпуклой вершине или отрицателен в вогнутой вершине. Для любого простого многоугольника сумма внешних углов равна $2\pi$ (один полный оборот, 360°). Таким образом, сумма внутренних углов простого многоугольника с $n$ стороны это $(n-2)\pi$ . ^[14]

Любой простой многоугольник можно разбить на непересекающиеся треугольники с помощью подмножества его диагоналей. Когда многоугольник имеет $n$ стороны, это производит $n-2$ треугольники, разделенные $n-3$ диагонали. Полученное разбиение называется триангуляцией многоугольника . ^[8] Форма простого треугольного многоугольника может быть однозначно определена внутренними углами многоугольника и перекрестными отношениями четырехугольников , образованных парами треугольников, имеющих общую диагональ. ^[15]

Согласно теореме о двух ушках , каждый простой многоугольник, не являющийся треугольником, имеет как минимум два уха — вершины, два соседа которых являются конечными точками диагонали. ^[8] Связанная с этим теорема утверждает, что каждый простой многоугольник, который не является выпуклым многоугольником, имеет рот , вершину, два соседа которой являются конечными точками отрезка прямой, который в противном случае полностью находится вне многоугольника. Многоугольники, у которых ровно два уха и один рот, называются антропоморфными многоугольниками . ^[16]

По теореме о картинной галерее в простом многоугольнике с $n$ вершин, всегда можно найти подмножество не более $\lfloor n/3\rfloor$ вершин со свойством, что каждая точка многоугольника видна из одной из выбранных вершин. Это означает, что для каждой точки $p$ в многоугольнике существует отрезок, соединяющий $p$ к выбранной вершине, проходя только через внутренние точки многоугольника. Один из способов доказать это — использовать раскраску графа при триангуляции многоугольника: всегда можно раскрасить вершины в три цвета так, чтобы каждая сторона или диагональ в триангуляции имела две конечные точки разных цветов. Каждая точка многоугольника видна вершине каждого цвета, например, одной из трех вершин треугольника, содержащего эту точку в выбранной триангуляции. Один из цветов используется не более чем $\lfloor n/3\rfloor$ вершин, что доказывает теорему. ^[17]

Особые случаи [ править ]

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

Монотонный многоугольник относительно прямой линии. $L$ , представляет собой многоугольник, для которого каждая линия, перпендикулярная $L$ пересекает внутреннюю часть многоугольника в связном множестве. Эквивалентно, это многоугольник, граница которого может быть разделена на две монотонные многоугольные цепи, подпоследовательности ребер, вершины которых, если проецироваться перпендикулярно на $L$ , имеют одинаковый порядок вдоль $L$ как они это делают в цепочке. ^[18]

Вычислительные задачи [ править ]

Чтобы проверить, находится ли точка внутри многоугольника, постройте любой луч, исходящий из точки, и посчитайте его пересечения с многоугольником. Если она пересекает только внутренние точки ребер нечетное количество раз, точка лежит внутри многоугольника; если даже, то точка лежит снаружи. Лучи, проходящие через вершины многоугольника или содержащие его края, требуют особого внимания. ^[19]

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

Точка при тестировании полигона включает в себя определение для простого многоугольника $P$ и точка запроса $q$ , ли $q$ лежит внутри $P$ . Ее можно решить за линейное время ; в качестве альтернативы можно преобразовать данный многоугольник в структуру данных за линейное время, так что последующие проверки точек в многоугольнике могут выполняться за логарифмическое время. ^[20]
Известны простые формулы для вычисления площади внутренней части многоугольника. К ним относятся формула шнурков для произвольных многоугольников, ^[21] и теорема Пика для многоугольников с целочисленными координатами вершин. ^[12]^[22]
Выпуклую оболочку простого многоугольника также можно найти за линейное время, быстрее, чем алгоритмы поиска выпуклых оболочек точек, не соединенных в многоугольник. ^[6]
Построение триангуляции простого многоугольника также можно выполнить за линейное время, хотя алгоритм сложен. Модификацию того же алгоритма можно также использовать для проверки того, образует ли замкнутая ломаная цепь простой многоугольник (то есть, избегает ли она самопересечений) за линейное время. ^[23] Это также приводит к алгоритму с линейным временем для решения задачи художественной галереи, используя не более $\lfloor n/3\rfloor$ точек, хотя и не обязательно с использованием оптимального количества точек для данного многоугольника. ^[24] Хотя можно преобразовать любые две триангуляции одного и того же многоугольника друг в друга с помощью переворотов , которые заменяют одну диагональ за раз, определение того, можно ли это сделать, используя только ограниченное количество переворотов, является NP-полным . ^[25]
Геодезический , путь ^[26] кратчайший путь на плоскости, который соединяет две точки внутри многоугольника, не пересекая его снаружи, может быть найден за линейное время с помощью алгоритма, использующего триангуляцию в качестве подпрограммы. ^[27] То же самое верно и для геодезического центра — точки многоугольника, которая минимизирует максимальную длину его геодезических путей ко всем остальным точкам. ^[26]
Многоугольник видимости внутренней точки простого многоугольника, то есть точек, которые непосредственно видны из данной точки по отрезкам линий, внутренними по отношению к многоугольнику, может быть построен за линейное время. ^[28] То же самое относится и к подмножеству, которое видно хотя бы из одной точки данного отрезка. ^[27]

Другие вычислительные проблемы, изучаемые для простых многоугольников, включают построение самой длинной диагонали или самого длинного отрезка внутренней части многоугольника, ^[13] выпуклого черепа (самого большого выпуклого многоугольника внутри данного простого многоугольника), ^[29]^[30] и различных одномерных скелетов, аппроксимирующих его форму, включая медиальную ось. ^[31] и прямой скелет . ^[32] Исследователи также изучили создание других многоугольников из простых многоугольников, используя их кривые смещения . ^[33] союзы и пересечения, ^[11] и суммы Минковского , ^[34] но эти операции не всегда создают в результате простой многоугольник. Их можно определить таким образом, чтобы всегда создавать двумерную область, но это требует тщательного определения операций пересечения и разности, чтобы избежать создания одномерных объектов или изолированных точек. ^[11]

Родственные конструкции [ править ]

Согласно теореме Римана об отображении , любое односвязное открытое подмножество плоскости можно конформно отобразить на диск. Отображение Шварца – Кристоффеля предоставляет метод явного построения карты диска в любой простой многоугольник с использованием заданных углов вершин и прообразов вершин многоугольника на границе диска. Эти предвершины обычно вычисляются численно. ^[35]

Каждый конечный набор точек на плоскости, который не лежит на одной прямой, можно соединить, образуя вершины простого многоугольника (с учетом углов 180 °); например, один из таких многоугольников является решением задачи коммивояжера . ^[36] Соединение точек для формирования многоугольника таким способом называется полигонализацией . ^[37]

Каждый простой многоугольник может быть представлен формулой конструктивной объемной геометрии , которая строит многоугольник (как замкнутое множество, включая внутреннюю часть) из объединений и пересечений полуплоскостей , при этом каждая сторона многоугольника появляется один раз как полуплоскость в формула. Преобразование $n$ односторонний многоугольник в это представление можно выполнить за время $O(n\log n)$ . ^[38]

Граф видимости простого многоугольника соединяет его вершины рёбрами, представляющими стороны и диагонали многоугольника. ^[3] Он всегда содержит гамильтонов цикл , образованный сторонами многоугольника. Вычислительная сложность реконструкции многоугольника, который имеет заданный граф в качестве графа видимости и с заданным гамильтоновым циклом в качестве цикла сторон, остается открытой проблемой. ^[39]

См. также [ править ]

Задача правила Карпентера о непрерывном движении простого многоугольника в выпуклый многоугольник.
Теорема Эрдеша – Надя , процесс отражения карманов невыпуклого простого многоугольника, чтобы сделать его выпуклым.
Сеть (многогранник) — простой многоугольник, который можно сложить и склеить, чтобы образовать заданный многогранник.
Сферический многоугольник , аналогичная концепция на поверхности сферы.
Слабо простой многоугольник — обобщение простых многоугольников, позволяющее краям соприкасаться ограниченным количеством способов.

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

^ Милнор, Джон В. (1950). «О полной кривизне узлов». Анналы математики . 2-я серия. 52 : 248–257. дои : 10.2307/1969467 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж Препарата, Франко П .; Шамос, Майкл Ян (1985). Вычислительная геометрия: Введение . Тексты и монографии по информатике. Спрингер-Верлаг. п. 18. дои : 10.1007/978-1-4612-1098-6 . ISBN 978-1-4612-1098-6 .
^ Jump up to: Перейти обратно: ^а ^б Эверетт, Хейзел; Корнейл, Дерек (1995). «Отрицательные результаты по характеристике графиков видимости». Вычислительная геометрия: теория и приложения . 5 (2): 51–63. дои : 10.1016/0925-7721(95)00021-Z . МР 1353288 .
^ Аронов, Борис ; Зейдель, Раймунд ; Сувен, Дайан (1993). «О согласованных триангуляциях простых многоугольников» . Вычислительная геометрия: теория и приложения . 3 (1): 27–35. дои : 10.1016/0925-7721(93)90028-5 . МР 1222755 .
^ Малкевич, Джозеф (2016). «Являются ли точные определения хорошей идеей?» . Столбец функций AMS . Американское математическое общество.
^ Jump up to: Перейти обратно: ^а ^б МакКаллум, Дункан; Авис, Дэвид (1979). «Линейный алгоритм поиска выпуклой оболочки простого многоугольника». Письма об обработке информации . 9 (5): 201–206. дои : 10.1016/0020-0190(79)90069-3 . МР 0552534 .
^ де Берг, М .; ван Кревелд, М .; Овермарс, Марк ; Шварцкопф, О. (2008). Вычислительная геометрия: алгоритмы и приложения (3-е изд.). Спрингер. п. 58. дои : 10.1007/978-3-540-77974-2 .
^ Jump up to: Перейти обратно: ^а ^б ^с Мейстерс, GH (1975). «У многоугольников есть уши». Американский математический ежемесячник . 82 (6): 648–651. дои : 10.2307/2319703 . JSTOR 2319703 . МР 0367792 .
^ Хейлз, Томас К. (2007). «Доказательство Джордана теоремы о кривой Жордана» (PDF) . От понимания к доказательству: Фестиваль в честь Анджея Трибулца. Исследования по логике, грамматике и риторике . 10 (23). Белостокский университет.
^ Томассен, Карстен (1992). «Теорема Джордана-Шенфлиса и классификация поверхностей». Американский математический ежемесячник . 99 (2): 116–130. дои : 10.1080/00029890.1992.11995820 . JSTOR 2324180 . МР 1144352 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Маргалит, Авраам; Нотт, Гэри Д. (1989). «Алгоритм вычисления объединения, пересечения или разности двух многоугольников». Компьютеры и графика . 13 (2): 167–183. дои : 10.1016/0097-8493(89)90059-9 .
^ Jump up to: Перейти обратно: ^а ^б Нивен, Иван ; Цукерман, HS (1967). «Точки решетки и многоугольная площадь». Американский математический ежемесячник . 74 (10): 1195–1200. дои : 10.1080/00029890.1967.12000095 . JSTOR 2315660 . МР 0225216 .
^ Jump up to: Перейти обратно: ^а ^б Аггарвал, Алок; Сури, Субхаш (1990). «Вычисление наибольшей диагонали простого многоугольника». Письма об обработке информации . 35 (1): 13–18. дои : 10.1016/0020-0190(90)90167-В . МР 1069001 .
^ Ричмонд, Беттина ; Ричмонд, Томас (2023). Дискретный переход к высшей математике . Чистые и прикладные тексты для студентов. Том. 63 (2-е изд.). Американское математическое общество. п. 421. ИСБН 9781470472047 .
^ Снойинк, Джек (1999). «Перекрестные отношения и углы определяют многоугольник» . Дискретная и вычислительная геометрия . 22 (4): 619–631. дои : 10.1007/PL00009481 . МР 1721028 .
^ Туссен, Годфрид (1991). «Антропоморфные многоугольники». Американский математический ежемесячник . 98 (1): 31–35. дои : 10.2307/2324033 . JSTOR 2324033 . МР 1083611 .
^ Фиск, С. (1978). «Краткое доказательство теоремы сторожа Хваталя» . Журнал комбинаторной теории, серия B. 24 (3): 374. doi : 10.1016/0095-8956(78)90059-X .
^ Препарата, Франко П .; Суповит, Кеннет Дж. (1981). «Проверка простого многоугольника на монотонность». Письма об обработке информации . 12 (4): 161–164. дои : 10.1016/0020-0190(81)90091-0 .
^ Ширра, Стефан (2008). «Насколько надежны практические стратегии «точка в полигоне»?» (PDF) . В Гальперине, Дэн; Мельхорн, Курт (ред.). Алгоритмы – ESA 2008, 16-й ежегодный европейский симпозиум, Карлсруэ, Германия, 15–17 сентября 2008 г. Материалы . Конспекты лекций по информатике. Том. 5193. Спрингер. стр. 744–755. дои : 10.1007/978-3-540-87744-8_62 .
^ Снойинк, Джек (2017). «Расположение точки» (PDF) . В Тоте, Чаба Д.; О'Рурк, Джозеф; Гудман, Джейкоб Э. (ред.). Справочник по дискретной и вычислительной геометрии (3-е изд.). Чепмен и Холл/CRC. стр. 1005–1023.
^ Брейден, Барт (1986). «Формула площади геодезиста» (PDF) . Математический журнал колледжа . 17 (4): 326–337. дои : 10.2307/2686282 . JSTOR 2686282 . Архивировано из оригинала (PDF) 7 ноября 2012 г.
^ Грюнбаум, Бранко ; Шепард, GC (февраль 1993 г.). «Теорема Пика». Американский математический ежемесячник . 100 (2): 150–161. дои : 10.2307/2323771 . JSTOR 2323771 . МР 1212401 .
^ Шазель, Бернар (1991). «Триангуляция простого многоугольника за линейное время» . Дискретная и вычислительная геометрия . 6 (5): 485–524. дои : 10.1007/BF02574703 . МР 1115104 .
^ Уррутия, Хорхе (2000). «Картинная галерея и проблемы освещения». В Саке, Йорг-Рюдигер ; Уррутия, Хорхе (ред.). Справочник по вычислительной геометрии . Амстердам: Северная Голландия. стр. 973–1027. дои : 10.1016/B978-044482537-7/50023-1 . ISBN 0-444-82537-1 . МР 1746693 .
^ Айххольцер, Освин; Мюльцер, Вольфганг; Пильц, Александр (2015). «Расстояние переворота между триангуляциями простого многоугольника NP-полное». Дискретная и вычислительная геометрия . 54 (2): 368–389. arXiv : 1209.0579 . дои : 10.1007/s00454-015-9709-7 . МР 3372115 .
^ Jump up to: Перейти обратно: ^а ^б Ан, Хи-Кап; Барба, Луис; Бозе, Просенджит ; Де Каруфель, Жан-Лу; Корман, Матиас; О, Ынджин (2016). «Алгоритм линейного времени для геодезического центра простого многоугольника». Дискретная и вычислительная геометрия . 56 (4): 836–859. arXiv : 1501.00561 . дои : 10.1007/s00454-016-9796-0 . МР 3561791 .
^ Jump up to: Перейти обратно: ^а ^б Гибас, Леонидас ; Хершбергер, Джон ; Левен, Дэниел; Шарир, Миша ; Тарьян, Роберт Э. (1987). «Алгоритмы линейного времени для решения задач видимости и кратчайшего пути внутри триангулированных простых многоугольников». Алгоритмика . 2 (2): 209–233. дои : 10.1007/BF01840360 . МР 0895445 .
^ Эль Джинди, Хосам; Авис, Дэвид (1981). «Линейный алгоритм расчета многоугольника видимости из точки». Журнал алгоритмов . 2 (2): 186–197. дои : 10.1016/0196-6774(81)90019-5 .
^ Чанг, Дж. С.; Яп, К.-К. (1986). «Полиномиальное решение задачи о чистке картофеля» . Дискретная и вычислительная геометрия . 1 (2): 155–182. дои : 10.1007/BF02187692 . МР 0834056 .
^ Кабельо, Серджио; Цибулка, Йозеф; Кынчл, Ян; Сомелл, Мария; Валтр, Павел (2017). «Очистка картофеля почти оптимально за почти линейное время». SIAM Journal по вычислительной технике . 46 (5): 1574–1602. arXiv : 1406.1368 . дои : 10.1137/16M1079695 . МР 3708542 .
^ Чин, Фрэнсис YL ; Снойинк, Джек; Ван, Цао Ань (1999). «Нахождение средней оси простого многоугольника за линейное время» . Дискретная и вычислительная геометрия . 21 (3): 405–420. дои : 10.1007/PL00009429 . МР 1672988 .
^ Ченг, Сиу-Винг; Менсель, Лиам; Виньерон, Антуан (2016). «Более быстрый алгоритм расчета прямых скелетов». Транзакции ACM на алгоритмах . 12 (3): 44:1–44:21. arXiv : 1405.4691 . дои : 10.1145/2898961 .
^ Палфрадер, Питер; Хелд, Мартин (февраль 2015 г.). «Расчет кривых смещения под углом на основе прямых каркасов» . Компьютерное проектирование и приложения . 12 (4): 414–424. дои : 10.1080/16864360.2014.997637 .
^ Окс, Эдуард; Шарир, Миша (2006). «Суммы Минковского монотонных и общих простых многоугольников» . Дискретная и вычислительная геометрия . 35 (2): 223–240. дои : 10.1007/s00454-005-1206-y . МР 2195052 .
^ Трефетен, Ллойд Н .; Дрисколл, Тобин А. (1998). «Картирование Шварца – Кристоффеля в компьютерную эпоху». Труды Международного конгресса математиков, Vol. III (Берлин, 1998 г.) . Документа Математика. стр. 533–542. МР 1648186 .
^ Кинтас, LV; Супник, Фред (1965). «О некоторых свойствах кратчайших гамильтоновых цепей». Американский математический ежемесячник . 72 (9): 977–980. дои : 10.2307/2313333 . JSTOR 2313333 . МР 0188872 .
^ Демейн, Эрик Д .; Фекете, Шандор П.; Кельденич, Филипп; Крупке, Доминик; Митчелл, Джозеф С.Б. (2022). «Простые полигонализации, оптимальные по площади: задача компьютерной графики 2019». Журнал экспериментальной алгоритмики ACM . 27 : А2.4:1–12. дои : 10.1145/3504000 . hdl : 1721.1/146480 . МР 4390039 .
^ Добкин, Дэвид ; Гибас, Леонидас ; Хершбергер, Джон ; Снойинк, Джек (1993). «Эффективный алгоритм поиска CSG-представления простого многоугольника». Алгоритмика . 10 (1): 1–23. дои : 10.1007/BF01908629 . МР 1230699 .
^ Гош, Субир Кумар; Госвами, Партха П. (2013). «Нерешенные проблемы графов видимости точек, отрезков и многоугольников». Обзоры вычислительной техники ACM . 46 (2): 22:1–22:29. arXiv : 1012.5187 . дои : 10.1145/2543581.2543589 .

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

Вайсштейн, Эрик В. «Простой многоугольник» . Математический мир .

[milnor-1] Милнор, Джон В. (1950). «О полной кривизне узлов». Анналы математики . 2-я серия. 52 : 248–257. дои : 10.2307/1969467 .

[preparata-shamos-2] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж Препарата, Франко П .; Шамос, Майкл Ян (1985). Вычислительная геометрия: Введение . Тексты и монографии по информатике. Спрингер-Верлаг. п. 18. дои : 10.1007/978-1-4612-1098-6 . ISBN 978-1-4612-1098-6 .

[everett-corneil-3] Jump up to: Перейти обратно: ^а ^б Эверетт, Хейзел; Корнейл, Дерек (1995). «Отрицательные результаты по характеристике графиков видимости». Вычислительная геометрия: теория и приложения . 5 (2): 51–63. дои : 10.1016/0925-7721(95)00021-Z . МР 1353288 .

[compatible-4] Аронов, Борис ; Зейдель, Раймунд ; Сувен, Дайан (1993). «О согласованных триангуляциях простых многоугольников» . Вычислительная геометрия: теория и приложения . 3 (1): 27–35. дои : 10.1016/0925-7721(93)90028-5 . МР 1222755 .

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

[mccallum-avis-6] Jump up to: Перейти обратно: ^а ^б МакКаллум, Дункан; Авис, Дэвид (1979). «Линейный алгоритм поиска выпуклой оболочки простого многоугольника». Письма об обработке информации . 9 (5): 201–206. дои : 10.1016/0020-0190(79)90069-3 . МР 0552534 .

[4marks-7] де Берг, М .; ван Кревелд, М .; Овермарс, Марк ; Шварцкопф, О. (2008). Вычислительная геометрия: алгоритмы и приложения (3-е изд.). Спрингер. п. 58. дои : 10.1007/978-3-540-77974-2 .

[meisters-8] Jump up to: Перейти обратно: ^а ^б ^с Мейстерс, GH (1975). «У многоугольников есть уши». Американский математический ежемесячник . 82 (6): 648–651. дои : 10.2307/2319703 . JSTOR 2319703 . МР 0367792 .

[hales-9] Хейлз, Томас К. (2007). «Доказательство Джордана теоремы о кривой Жордана» (PDF) . От понимания к доказательству: Фестиваль в честь Анджея Трибулца. Исследования по логике, грамматике и риторике . 10 (23). Белостокский университет.

[thomassen-10] Томассен, Карстен (1992). «Теорема Джордана-Шенфлиса и классификация поверхностей». Американский математический ежемесячник . 99 (2): 116–130. дои : 10.1080/00029890.1992.11995820 . JSTOR 2324180 . МР 1144352 .

[margalit-knott-11] Jump up to: Перейти обратно: ^а ^б ^с ^д Маргалит, Авраам; Нотт, Гэри Д. (1989). «Алгоритм вычисления объединения, пересечения или разности двух многоугольников». Компьютеры и графика . 13 (2): 167–183. дои : 10.1016/0097-8493(89)90059-9 .

[niven-zuckerman-12] Jump up to: Перейти обратно: ^а ^б Нивен, Иван ; Цукерман, HS (1967). «Точки решетки и многоугольная площадь». Американский математический ежемесячник . 74 (10): 1195–1200. дои : 10.1080/00029890.1967.12000095 . JSTOR 2315660 . МР 0225216 .

[aggarwal-suri-13] Jump up to: Перейти обратно: ^а ^б Аггарвал, Алок; Сури, Субхаш (1990). «Вычисление наибольшей диагонали простого многоугольника». Письма об обработке информации . 35 (1): 13–18. дои : 10.1016/0020-0190(90)90167-В . МР 1069001 .

[rich2-14] Ричмонд, Беттина ; Ричмонд, Томас (2023). Дискретный переход к высшей математике . Чистые и прикладные тексты для студентов. Том. 63 (2-е изд.). Американское математическое общество. п. 421. ИСБН 9781470472047 .

[cross-ratio-15] Снойинк, Джек (1999). «Перекрестные отношения и углы определяют многоугольник» . Дискретная и вычислительная геометрия . 22 (4): 619–631. дои : 10.1007/PL00009481 . МР 1721028 .

[toussaint-16] Туссен, Годфрид (1991). «Антропоморфные многоугольники». Американский математический ежемесячник . 98 (1): 31–35. дои : 10.2307/2324033 . JSTOR 2324033 . МР 1083611 .

[fisk-17] Фиск, С. (1978). «Краткое доказательство теоремы сторожа Хваталя» . Журнал комбинаторной теории, серия B. 24 (3): 374. doi : 10.1016/0095-8956(78)90059-X .

[preparata-supowit-18] Препарата, Франко П .; Суповит, Кеннет Дж. (1981). «Проверка простого многоугольника на монотонность». Письма об обработке информации . 12 (4): 161–164. дои : 10.1016/0020-0190(81)90091-0 .

[schirra-19] Ширра, Стефан (2008). «Насколько надежны практические стратегии «точка в полигоне»?» (PDF) . В Гальперине, Дэн; Мельхорн, Курт (ред.). Алгоритмы – ESA 2008, 16-й ежегодный европейский симпозиум, Карлсруэ, Германия, 15–17 сентября 2008 г. Материалы . Конспекты лекций по информатике. Том. 5193. Спрингер. стр. 744–755. дои : 10.1007/978-3-540-87744-8_62 .

[snoeyink-20] Снойинк, Джек (2017). «Расположение точки» (PDF) . В Тоте, Чаба Д.; О'Рурк, Джозеф; Гудман, Джейкоб Э. (ред.). Справочник по дискретной и вычислительной геометрии (3-е изд.). Чепмен и Холл/CRC. стр. 1005–1023.

[braden-21] Брейден, Барт (1986). «Формула площади геодезиста» (PDF) . Математический журнал колледжа . 17 (4): 326–337. дои : 10.2307/2686282 . JSTOR 2686282 . Архивировано из оригинала (PDF) 7 ноября 2012 г.

[grunbaum-shephard-22] Грюнбаум, Бранко ; Шепард, GC (февраль 1993 г.). «Теорема Пика». Американский математический ежемесячник . 100 (2): 150–161. дои : 10.2307/2323771 . JSTOR 2323771 . МР 1212401 .

[chazelle-23] Шазель, Бернар (1991). «Триангуляция простого многоугольника за линейное время» . Дискретная и вычислительная геометрия . 6 (5): 485–524. дои : 10.1007/BF02574703 . МР 1115104 .

[urrutia-24] Уррутия, Хорхе (2000). «Картинная галерея и проблемы освещения». В Саке, Йорг-Рюдигер ; Уррутия, Хорхе (ред.). Справочник по вычислительной геометрии . Амстердам: Северная Голландия. стр. 973–1027. дои : 10.1016/B978-044482537-7/50023-1 . ISBN 0-444-82537-1 . МР 1746693 .

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

[abbcko-26] Jump up to: Перейти обратно: ^а ^б Ан, Хи-Кап; Барба, Луис; Бозе, Просенджит ; Де Каруфель, Жан-Лу; Корман, Матиас; О, Ынджин (2016). «Алгоритм линейного времени для геодезического центра простого многоугольника». Дискретная и вычислительная геометрия . 56 (4): 836–859. arXiv : 1501.00561 . дои : 10.1007/s00454-016-9796-0 . МР 3561791 .

[ghlst-27] Jump up to: Перейти обратно: ^а ^б Гибас, Леонидас ; Хершбергер, Джон ; Левен, Дэниел; Шарир, Миша ; Тарьян, Роберт Э. (1987). «Алгоритмы линейного времени для решения задач видимости и кратчайшего пути внутри триангулированных простых многоугольников». Алгоритмика . 2 (2): 209–233. дои : 10.1007/BF01840360 . МР 0895445 .

[avis-elgindy-28] Эль Джинди, Хосам; Авис, Дэвид (1981). «Линейный алгоритм расчета многоугольника видимости из точки». Журнал алгоритмов . 2 (2): 186–197. дои : 10.1016/0196-6774(81)90019-5 .

[chang-yap-29] Чанг, Дж. С.; Яп, К.-К. (1986). «Полиномиальное решение задачи о чистке картофеля» . Дискретная и вычислительная геометрия . 1 (2): 155–182. дои : 10.1007/BF02187692 . МР 0834056 .

[ccksv-30] Кабельо, Серджио; Цибулка, Йозеф; Кынчл, Ян; Сомелл, Мария; Валтр, Павел (2017). «Очистка картофеля почти оптимально за почти линейное время». SIAM Journal по вычислительной технике . 46 (5): 1574–1602. arXiv : 1406.1368 . дои : 10.1137/16M1079695 . МР 3708542 .

[csl-31] Чин, Фрэнсис YL ; Снойинк, Джек; Ван, Цао Ань (1999). «Нахождение средней оси простого многоугольника за линейное время» . Дискретная и вычислительная геометрия . 21 (3): 405–420. дои : 10.1007/PL00009429 . МР 1672988 .

[cmv-32] Ченг, Сиу-Винг; Менсель, Лиам; Виньерон, Антуан (2016). «Более быстрый алгоритм расчета прямых скелетов». Транзакции ACM на алгоритмах . 12 (3): 44:1–44:21. arXiv : 1405.4691 . дои : 10.1145/2898961 .

[palfrader-held-33] Палфрадер, Питер; Хелд, Мартин (февраль 2015 г.). «Расчет кривых смещения под углом на основе прямых каркасов» . Компьютерное проектирование и приложения . 12 (4): 414–424. дои : 10.1080/16864360.2014.997637 .

[oks-sharir-34] Окс, Эдуард; Шарир, Миша (2006). «Суммы Минковского монотонных и общих простых многоугольников» . Дискретная и вычислительная геометрия . 35 (2): 223–240. дои : 10.1007/s00454-005-1206-y . МР 2195052 .

[trefethen-driscoll-35] Трефетен, Ллойд Н .; Дрисколл, Тобин А. (1998). «Картирование Шварца – Кристоффеля в компьютерную эпоху». Труды Международного конгресса математиков, Vol. III (Берлин, 1998 г.) . Документа Математика. стр. 533–542. МР 1648186 .

[quintas-supnick-36] Кинтас, LV; Супник, Фред (1965). «О некоторых свойствах кратчайших гамильтоновых цепей». Американский математический ежемесячник . 72 (9): 977–980. дои : 10.2307/2313333 . JSTOR 2313333 . МР 0188872 .

[dfkkm-37] Демейн, Эрик Д .; Фекете, Шандор П.; Кельденич, Филипп; Крупке, Доминик; Митчелл, Джозеф С.Б. (2022). «Простые полигонализации, оптимальные по площади: задача компьютерной графики 2019». Журнал экспериментальной алгоритмики ACM . 27 : А2.4:1–12. дои : 10.1145/3504000 . hdl : 1721.1/146480 . МР 4390039 .

[dghs-38] Добкин, Дэвид ; Гибас, Леонидас ; Хершбергер, Джон ; Снойинк, Джек (1993). «Эффективный алгоритм поиска CSG-представления простого многоугольника». Алгоритмика . 10 (1): 1–23. дои : 10.1007/BF01908629 . МР 1230699 .

[ghosh-goswami-39] Гош, Субир Кумар; Госвами, Партха П. (2013). «Нерешенные проблемы графов видимости точек, отрезков и многоугольников». Обзоры вычислительной техники ACM . 46 (2): 22:1–22:29. arXiv : 1012.5187 . дои : 10.1145/2543581.2543589 .

[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]

[33]

[34]

[35]

[36]

[37]

[38]

[39]