Теорема Эрдёша — Сёкефальви-Надя

Теорема Эрдёша — Сёкефальви-Надя — результат в комбинаторной геометрии, согласно которому многоугольник без самопересечений может быть преобразован в выпуклый многоугольник путём конечного числа зеркальных отражений «карманов» — связных компонентов выпуклой оболочки. На каждом шаге определяется выпуклая оболочка многоугольника, и её ребро, относительно которого осуществляется отражение. Конечный многоугольник может иметь параллельные смежные рёбра, то есть быть слабо выпуклым. Помимо отражения, карман может быть преобразован поворотом на 180° относительно центра ребра оболочки. Такое преобразование оказывается более эффективным средством достижения выпуклости многоугольника^[1].

Гипотезу сформулировал Пал Эрдёш в 1935 году и опубликовал в журнале American Mathematical Monthly. В 1939 году Сёкефальви-Надь доказал и опубликовал теорему.

Теорема

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

История

Теорема имеет курьёзную историю и была неоднократно передоказана. В 1995 году Бранко Грюнбаум обнаружил в оригинальном доказательстве малозаметную ошибку, которую ему удалось устранить.

Вариации и обобщения

Джосс и Шеннон доказали, что требуемое число отражений нельзя ограничить даже для четырехугольников. Они также дали оценку на число поворотов.
- Любой $n$ -угольник без самопересечений может быть преобразован в слабо выпуклый не более чем $(n-1)!$ поворотом карманов относительно ребер выпуклой оболочки.
  - Авторы теоремы выдвинули гипотезу, что на самом деле достаточно ${\frac {1}{4}}n^{2}$ поворотов^[2]. На 2013 год она не доказана.
- Тереома Грюнбаума — Закса: Любой многоугольник может быть преобразован в слабо выпуклый конечным числом поворотов карманов относительно ребер выпуклой оболочки.

Примечания

↑ Бранко Грюнбраум и Джозеф Закс. Convexification of polygons by flips and by flipturns // Discrete Math. — 2001. — Т. 241. — С. 333—342. Архивировано 30 мая 2013 года.
↑ Бранко Грюнбаум. How to convexify a polygon // Geombinatorics. — 1995. — № 5. — С. 24—30.

Литература

Годфрид Туссен. The Erdős-Nagy Theorem and its Ramifications // Proc. 11th Canadian Conference on Computational Geometry. — 1999. — С. 219—236.
Э. Д. Демайне, B. Gassend, Дж. О’Рурке, G.T. Toussaint. All polygons flip finitely right? Surveys on discrete and computational geometry // Contemp. Math. — Providence, RI: Amer. Math. Soc, 2008. — Т. 453. — С. 231—255.

Ссылки

The convexification of a simple polygon

[1] Бранко Грюнбраум и Джозеф Закс. Convexification of polygons by flips and by flipturns // Discrete Math. — 2001. — Т. 241. — С. 333—342. Архивировано 30 мая 2013 года.

[2] Бранко Грюнбаум. How to convexify a polygon // Geombinatorics. — 1995. — № 5. — С. 24—30.

[1]

[2]