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

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

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

Формулировка теоремы

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

Связь с триангуляциями

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

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

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

Родственные типы вершин

Многоугольник только с двумя ушками (светлая штриховка), ни одно из которых не показано.

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

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

История и доказательства

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

Внешние ссылки

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