Выпуклый многоугольник

Многоугольник, являющийся границей выпуклого множества

Пример выпуклого многоугольника: правильный пятиугольник.

В геометрии выпуклый многоугольник — это многоугольник , являющийся границей выпуклого множества . Это означает, что отрезок между двумя точками многоугольника содержится в объединении внутренней части и границы многоугольника. В частности, это простой многоугольник (не самопересекающийся ). ^[1] Аналогично, многоугольник является выпуклым, если каждая линия , не содержащая ребер, пересекает многоугольник не более чем в двух точках.

Строго выпуклый многоугольник — это выпуклый многоугольник, ни одна прямая которого не содержит двух его ребер. В выпуклом многоугольнике все внутренние углы меньше или равны 180 градусов, а в строго выпуклом многоугольнике все внутренние углы строго меньше 180 градусов.

Характеристики

Следующие свойства простого многоугольника эквивалентны выпуклости:

• Каждый внутренний угол меньше или равен 180 градусам .
• Каждая точка на каждом отрезке между двумя точками внутри или на границе многоугольника остается внутри или на границе.
• Многоугольник целиком содержится в замкнутой полуплоскости, определяемой каждым из его ребер.
• Для каждого ребра все внутренние точки находятся на одной стороне линии, которую определяет ребро.
• Угол при каждой вершине содержит все остальные вершины на своих ребрах и внутри.
• Многоугольник — это выпуклая оболочка его ребер.

Дополнительные свойства выпуклых многоугольников включают в себя:

• Пересечение двух выпуклых многоугольников является выпуклым многоугольником.
• Выпуклый многоугольник можно триангулировать за линейное время с помощью веерной триангуляции , состоящей в добавлении диагоналей от одной вершины ко всем остальным вершинам.
• Теорема Хелли : для каждого набора, состоящего как минимум из трех выпуклых многоугольников: если все пересечения всех многоугольников, кроме одного, непусты, то пересечение всех многоугольников непусто.
• Теорема Крейна-Милмана : Выпуклый многоугольник — это выпуклая оболочка его вершин. Таким образом, он полностью определяется набором своих вершин, и для восстановления всей формы многоугольника нужны только углы многоугольника.
• Теорема о разделении гиперплоскости : Любые два выпуклых многоугольника, не имеющие общих точек, имеют разделительную линию. Если многоугольники замкнутые и хотя бы один из них компактный, то существуют даже две параллельные линии-разделители (с зазором между ними).
• Свойство вписанного треугольника : из всех треугольников, содержащихся в выпуклом многоугольнике, существует треугольник максимальной площади, все вершины которого являются вершинами многоугольника. ^[2]
• Свойство вписывающего треугольника : каждый выпуклый многоугольник площади можно вписать в треугольник площади не более . Равенство справедливо (исключительно) для параллелограмма . ^[3] ${\displaystyle A}$ ${\displaystyle 2A}$
• Свойство вписанных/вписанных прямоугольников : для каждого выпуклого тела на плоскости мы можем вписать прямоугольник так , чтобы его гомотетическая копия была описана вокруг него , а положительный коэффициент гомотети не превышал 2 и . ^[4] ${\displaystyle C}$ ${\displaystyle r}$ ${\displaystyle C}$ ${\displaystyle R}$ ${\displaystyle r}$ ${\displaystyle C}$ ${\displaystyle 0.5{\text{ × Area}}(R)\leq {\text{Area}}(C)\leq 2{\text{ × Area}}(r)}$
• Средняя ширина выпуклого многоугольника равна его периметру, делённому на . То есть его ширина — это диаметр круга с тем же периметром, что и многоугольник. ^[5] ${\displaystyle \pi }$

Каждый многоугольник, вписанный в окружность (такой, что все вершины многоугольника касаются окружности), если не является самопересекающимся , является выпуклым. Однако не всякий выпуклый многоугольник можно вписать в окружность.

Строгая выпуклость

Следующие свойства простого многоугольника эквивалентны строгой выпуклости:

• Каждый внутренний угол строго меньше 180 градусов.
• Каждый отрезок линии между двумя точками внутри многоугольника или между двумя точками на границе, но не на одном и том же ребре, является строго внутренним по отношению к многоугольнику (за исключением его конечных точек, если они находятся на краях).
• Для каждого ребра внутренние точки и граничные точки, не входящие в ребро, находятся на одной стороне линии, которую определяет ребро.
• Угол при каждой вершине содержит все остальные вершины внутри себя (кроме данной вершины и двух соседних вершин).

Любой невырожденный треугольник строго выпуклый.

Смотрите также

• Выпуклая кривая  – тип плоской кривой.
• Вогнутый многоугольник  - простой невыпуклый многоугольник.
• Выпуклый многогранник  - Выпуклая оболочка конечного набора точек в евклидовом пространстве.
• Циклический многоугольник  – точки на общей окружности.Страницы с краткими описаниями целей перенаправления.
• Неявная кривая § Гладкая аппроксимация выпуклых многоугольников
• Тангенциальный многоугольник  - выпуклый многоугольник, содержащий вписанную окружность.

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

1. Определение и свойства выпуклых многоугольников с интерактивной анимацией.
2. Чандран, Шарат; Маунт, Дэвид М. (1992). «Параллельный алгоритм для вложенных и заключающих треугольников». Международный журнал вычислительной геометрии и приложений . 2 (2): 191–214. дои : 10.1142/S0218195992000123. МР  1168956.
3. Вайсштейн, Эрик В. «Описание треугольника». Математический мир Вольфрама .
4. Лассак, М. (1993). «Приближение выпуклых тел прямоугольниками». Геометрии посвященные . 47 : 111–117. дои : 10.1007/BF01263495. S2CID  119508642.
5. Белк, Джим. «Какова средняя ширина выпуклого многоугольника?». Математический обмен стеками .

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

• Вайсштейн, Эрик В. «Выпуклый многоугольник». Математический мир .
• http://www.rustycode.com/tutorials/convex.html
• Шорн, Питер; Фишер, Фредерик (1994), «I.2 Проверка выпуклости многоугольника», в Хекберте, Поле С. (редактор), Graphics Gems IV, Morgan Kaufmann (Academic Press), стр. 7–15, ISBN 9780123361554