Теорема о двух ушах

В геометрии теорема о двух ушах утверждает, что любой простой многоугольник с более чем тремя вершинами имеет по крайней мере два уха — вершины, которые можно удалить из многоугольника, не вводя никаких пересечений. Теорема о двух ушах эквивалентна существованию триангуляции многоугольника . Ее часто приписывают Гэри Х. Мейстерсу, но ранее ее доказал Макс Ден .

Простой многоугольник — это простая замкнутая кривая на евклидовой плоскости, состоящая из конечного числа отрезков в циклической последовательности, причем каждые два последовательных отрезка пересекаются в общей конечной точке и не имеют других пересечений. По теореме о кривой Жордана он разделяет плоскость на две области, одна из которых (внутренняя часть многоугольника) ограничена. Ухо многоугольника определяется как треугольник, образованный тремя последовательными вершинами многоугольника, таким образом, что его ребро полностью лежит внутри многоугольника. Теорема о двух ушах утверждает, что каждый простой многоугольник, который сам по себе не является треугольником, имеет по крайней мере два уха. ^[1]${\displaystyle u,v,w}$${\displaystyle uw}$

Ухо и два его соседа образуют треугольник внутри многоугольника, который не пересекается никакой другой частью многоугольника. Удаление треугольника такого типа дает многоугольник с меньшим количеством сторон, а многократное удаление ушей позволяет триангулировать любой простой многоугольник . И наоборот, если многоугольник триангулирован, слабый двойственный граф триангуляции (граф с одной вершиной на треугольник и одним ребром на пару смежных треугольников) будет деревом , и каждый лист дерева будет образовывать ухо. Поскольку каждое дерево с более чем одной вершиной имеет по крайней мере два листа, каждый триангулированный многоугольник с более чем одним треугольником имеет по крайней мере два уха. Таким образом, теорема о двух ушах эквивалентна тому факту, что каждый простой многоугольник имеет триангуляцию. ^[2]

Алгоритмы триангуляции, основанные на этом принципе, были названы алгоритмами отсечения ушей . Хотя наивная реализация медленная, отсечение ушей можно ускорить, наблюдая, что тройка последовательных вершин многоугольника образует ухо тогда и только тогда, когда центральная вершина тройки выпуклая, а тройка образует треугольник, не содержащий никаких рефлекторных вершин. Поддерживая очередь троек с этим свойством и многократно удаляя ухо из очереди и обновляя соседние тройки, можно выполнить отсечение ушей за время , где — число входных вершин, а — число рефлекторных вершин. ^[3]${\displaystyle O{\bigl (}n(r+1){\bigr )}}$${\displaystyle n}$${\displaystyle r}$

Если простой многоугольник триангулирован, то тройка последовательных вершин образует ухо, если является выпуклой вершиной и ни один из ее других соседей в триангуляции не лежит в треугольнике . Проверяя всех соседей всех вершин, можно найти все уши триангулированного простого многоугольника за линейное время . ^[4] В качестве альтернативы, также можно найти одно ухо простого многоугольника за линейное время, без триангуляции многоугольника. ^[5]${\displaystyle u,v,w}$${\displaystyle v}$${\displaystyle uvw}$

Ухо называется выставленным , когда его центральная вершина принадлежит выпуклой оболочке многоугольника. Однако многоугольник может не иметь выставленных ушей. ^[6]

Уши являются частным случаем главной вершины , вершины, такой, что отрезок прямой, соединяющий соседей вершины, не пересекает многоугольник и не касается никакой другой его вершины. Главная вершина, для которой этот отрезок прямой лежит вне многоугольника, называется ртом . Аналогично теореме о двух ушах, каждый невыпуклый простой многоугольник имеет по крайней мере один рот. Многоугольники с минимальным количеством главных вершин обоих типов, двумя ушами и ртом, называются антропоморфными многоугольниками . ^[7] Многократное нахождение и удаление рта из невыпуклого многоугольника в конечном итоге превратит его в выпуклую оболочку исходного многоугольника. Этот принцип можно применить к окружающим многоугольникам набора точек; это многоугольники, которые используют некоторые из точек в качестве вершин и содержат остальные из них. Удаление рта из окружающего полигона создает другой окружающий полигон, а семейство всех окружающих полигонов можно найти, обратив этот процесс удаления рта, начиная с выпуклой оболочки. ^[8]

Теорему о двух ушах часто приписывают статье 1975 года Гэри Х. Мейстерса, из которой и произошла терминология «ухо». ^[1] Однако теорема была доказана ранее Максом Деном (около 1899 г.) как часть доказательства теоремы о кривой Жордана . Чтобы доказать теорему, Ден замечает, что каждый многоугольник имеет по крайней мере три выпуклые вершины. Если одна из этих вершин, v , не является ухом, то ее можно соединить диагональю с другой вершиной x внутри треугольника uvw, образованного v и двумя ее соседями; x можно выбрать в качестве вершины внутри этого треугольника, которая находится дальше всего от прямой uw . Эта диагональ разбивает многоугольник на два меньших многоугольника, и повторное разложение по ушам и диагоналям в конечном итоге дает триангуляцию всего многоугольника, из которой ухо можно найти как лист двойственного дерева. ^[9]

• Теорема о двух ушах, Годфрид Туссен