Теорема о двух ушах - Википедия - Two ears theorem

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

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

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

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

Уши от триангуляции

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

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

Связанные типы вершин

Ухо называется незащищенный когда он образует вершину выпуклый корпус многоугольника. Однако у многоугольника могут не быть открытых ушей.[2]

Уши - частный случай главная вершина, вершина такая, что отрезок прямой, соединяющий соседей вершины, не пересекает многоугольник и не касается любой другой его вершины. Основная вершина, для которой этот отрезок прямой лежит вне многоугольника, называется рот. Аналогично теореме о двух ушах, у каждого невыпуклого простого многоугольника есть хотя бы один рот. Полигоны с минимальным количеством главных вершин обоих типов, два уха и рот, называются антропоморфные многоугольники.[3]

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

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

Рекомендации

  1. ^ О'Рурк, Джозеф (1987), Теоремы и алгоритмы художественной галереи, Международная серия монографий по информатике, Oxford University Press, ISBN  0-19-503965-3, МИСТЕР  0921437.
  2. ^ Мейстер, Г. Х. (1980), "Основные вершины, открытые точки и уши", Американский математический ежемесячный журнал, 87 (4): 284–285, Дои:10.2307/2321563, МИСТЕР  0567710.
  3. ^ Туссен, Годфрид (1991), «Антропоморфные многоугольники», Американский математический ежемесячный журнал, 98 (1): 31–35, Дои:10.2307/2324033, МИСТЕР  1083611.
  4. ^ Мейстер, Г. Х. (1975), «У многоугольников есть уши», Американский математический ежемесячный журнал, 82: 648–651, Дои:10.2307/2319703, МИСТЕР  0367792.
  5. ^ Гуггенхаймер, Х. (1977), «Теорема Жордана и неопубликованная рукопись Макса Дена» (PDF), Архив истории точных наук, 17 (2): 193–200, Дои:10.1007 / BF02464980, JSTOR  41133486, МИСТЕР  0532231.

внешняя ссылка