Теорема Эрдёша — Сёкефальви-Надя — результат в комбинаторной геометрии, согласно которому многоугольник без самопересечений может быть преобразован в выпуклый многоугольник путём конечного числа зеркальных отражений «карманов» — связных компонентов выпуклой оболочки. На каждом шаге определяется выпуклая оболочка многоугольника, и её ребро, относительно которого осуществляется отражение. Конечный многоугольник может иметь параллельные смежные рёбра, то есть быть слабо выпуклым. Помимо отражения, карман может быть преобразован поворотом на 180° относительно центра ребра оболочки. Такое преобразование оказывается более эффективным средством достижения выпуклости многоугольника[1].
Любой многоугольник без самопересечений может быть преобразован в слабо выпуклый конечным числом отражений карманов от ребер выпуклой оболочки.
История
Теорема имеет курьёзную историю и была неоднократно передоказана. В 1995 году Бранко Грюнбаум обнаружил в оригинальном доказательстве малозаметную ошибку, которую ему удалось устранить.
Вариации и обобщения
Джосс и Шеннон доказали, что требуемое число отражений нельзя ограничить даже для четырехугольников. Они также дали оценку на число поворотов.
Любой <math>n</math>-угольник без самопересечений может быть преобразован в слабо выпуклый не более чем <math> (n-1)!</math> поворотом карманов относительно ребер выпуклой оболочки.
Авторы теоремы выдвинули гипотезу, что на самом деле достаточно <math> \frac{1}{4} n^2</math> поворотов[2]. На 2013 год она не доказана.
Тереома Грюнбаума — Закса: Любой многоугольник может быть преобразован в слабо выпуклый конечным числом поворотов карманов относительно ребер выпуклой оболочки.
