В геометрии антропоморфный многоугольник - это простой многоугольник с двумя ушами и одним ртом . То есть для ровно трех вершин многоугольника отрезок линии, соединяющий двух соседей вершины, не пересекает многоугольник. Для двух из этих вершин (ушей) отрезок линии, соединяющий соседей, образует диагональ многоугольника, содержащегося внутри многоугольника. Для третьей вершины (устья) отрезок линии, соединяющий соседей, лежит за пределами многоугольника, образуя вход в вогнутость многоугольника. [1]
Каждый простой многоугольник имеет как минимум два уха (это теорема о двух ушах ), и каждый невыпуклый простой многоугольник имеет как минимум один рот, поэтому в некотором смысле антропоморфные многоугольники являются простейшими из возможных невыпуклых простых многоугольников. [1]
Можно распознать антропоморфные многоугольники за линейное время . [2]
Рекомендации
- ^ Б Туссен, Годфрид (1991), "Антропоморфные многоугольников", Американский Математический Ежемесячный , 98 (1): 31-35, DOI : 10,2307 / 2324033 , МР 1083611.
- ^ Шермер, Т .; Туссен, Г.Т. (1989), «Антропоморфные многоугольники можно распознать в линейном времени», в Яницки, Рышард; Кочкодай, Вальдемар В. (ред.), Труды Международной конференции по вычислениям и информации , Северная Голландия, стр. 117–123..