В геометрии теорема о двух ушах утверждает, что каждый простой многоугольник с более чем тремя вершинами имеет по крайней мере два уха , вершины, которые можно удалить из многоугольника без введения каких-либо пересечений. Теорема о двух ушах эквивалентна существованию триангуляции многоугольника . Его часто приписывают Гэри Х. Мейстеру, но ранее это доказал Макс Ден .
Формулировка теоремы
Ухо многоугольника определяется как вершина v такая, что отрезок прямой между двумя соседями v полностью лежит внутри многоугольника. Теорема о двух ушах утверждает, что каждый простой многоугольник имеет как минимум два уха.
Уши от триангуляции
Ухо и два его соседа образуют внутри многоугольника треугольник, который не пересекает никакая другая часть многоугольника. Удаление треугольника этого типа дает многоугольник с меньшим количеством сторон, а многократное удаление ушей позволяет триангулировать любой простой многоугольник .
И наоборот, если многоугольник триангулирован, слабый двойственный элемент триангуляции (граф с одной вершиной на треугольник и одним ребром на пару смежных треугольников) будет деревом, и каждый лист дерева будет образовывать ухо. Поскольку каждое дерево с более чем одной вершиной имеет как минимум два листа, каждый триангулированный многоугольник с более чем одним треугольником имеет как минимум два ушка. Таким образом, теорема о двух ушах эквивалентна тому факту, что каждый простой многоугольник имеет триангуляцию. [1]
Связанные типы вершин
Ухо называется оголенным, если оно образует вершину выпуклой оболочки многоугольника. Однако у многоугольника могут не быть открытых ушей. [2]
Уши - это частный случай главной вершины , такой вершины, что отрезок прямой, соединяющий соседей вершины, не пересекает многоугольник и не касается любой другой его вершины. Основная вершина, для которой этот отрезок прямой лежит вне многоугольника, называется устьем . По аналогии с теоремой о двух ушах, у каждого невыпуклого простого многоугольника есть хотя бы один рот. Многоугольники с минимальным числом главных вершин обоих типов, два уха и рот, называются антропоморфными многоугольниками . [3]
История и доказательства
Теорема о двух ушах часто приписывается статье Гэри Х. Мейстера 1975 года, из которой произошла терминология «ухо». [4] Однако теорема была доказана ранее Максом Деном (около 1899 г.) как часть доказательства теоремы о жордановой кривой . Чтобы доказать теорему, Ден замечает, что каждый многоугольник имеет не менее трех выпуклых вершин. Если одна из этих вершин, v , не является ухом, то ее можно соединить диагональю с другой вершиной x внутри треугольника uvw, образованного v и двумя его соседями; x можно выбрать в качестве вершины в этом треугольнике, наиболее удаленной от линии uw . Эта диагональ разбивает многоугольник на два меньших многоугольника, и повторное разбиение по ушам и диагоналям в конечном итоге приводит к триангуляции всего многоугольника, из которого можно найти ухо как лист двойного дерева. [5]
Рекомендации
- ^ О'Рурк, Джозеф (1987), Теоремы и алгоритмы художественной галереи , Международная серия монографий по информатике, Oxford University Press, ISBN 0-19-503965-3, Руководство по ремонту 0921437.
- ^ Meisters, GH (1980), "Основные вершины, открытые точки, и уши", American Mathematical Monthly , 87 (4): 284-285, DOI : 10,2307 / 2321563 , JSTOR 2321563 , MR 0567710.
- ^ Туссен, Godfried (1991), "Антропоморфные многоугольники", American Mathematical Monthly , 98 (1): 31-35, DOI : 10,2307 / 2324033 , JSTOR 2324033 , MR 1083611.
- ^ Meisters, GH (1975), "Полигоны есть уши", American Mathematical Monthly , 82 (6): 648-651, DOI : 10,2307 / 2319703 , JSTOR 2319703 , MR 0367792.
- ^ Guggenheimer, H. (1977), "Теорема жордановой кривой и неопубликованные рукописи Макса Дена" (PDF) , архив для истории точных наук , 17 (2): 193-200, DOI : 10.1007 / BF02464980 , JSTOR 41133486 , Руководство по ремонту 0532231.
Внешние ссылки
- Теорема Мейстера о двух ушах , перережь узел
- Теорема о двух ушах , Годфрид Туссен
- Вайсштейн, Эрик В. , "Теорема о двух ушах" , MathWorld