Теорема Эрдеша – Надя - Erdős–Nagy theorem
В Теорема Эрдеша – Надя это результат дискретная геометрия утверждая, что невыпуклый простой многоугольник можно превратить в выпуклый многоугольник конечной последовательностью флипов. Флипы определяются взятием выпуклая оболочка многоугольника и отражающий карман относительно граничного края. Теорема названа в честь математики Пол Эрдёш и Béla Szkefalvi-Nagy.
Заявление
А карман невыпуклого простого многоугольника - это простой многоугольник, ограниченный последовательной последовательностью ребер многоугольника вместе с одним ребром его выпуклый корпус это не край самого многоугольника. Таким образом, каждое выпуклое ребро корпуса, не являющееся ребром многоугольника, определяет карман. А кувырок кармана получается путем отражения краев многоугольника, ограничивающего карман, через линию отражения, содержащую выпуклый край корпуса. Поскольку отраженный карман полностью лежит в пределах отраженного изображения выпуклой оболочки на другой стороне этой линии, эта операция не может привести к пересечению, поэтому результатом переворота является другой простой многоугольник с большей площадью.
В некоторых случаях в результате однократного переворота невыпуклый простой многоугольник становится выпуклым. Как только это произойдет, перевороты станут невозможны. Теорема Эрдеша-Надя утверждает, что всегда можно найти последовательность переворотов, которая таким образом дает выпуклый многоугольник. Более того, для каждого простого многоугольника каждая последовательность переворотов в конечном итоге будет создать выпуклый многоугольник за конечное число шагов.
Существуют четырехугольники, требующие выпуклости сколь угодно большого (но конечного) числа флипов. Следовательно, невозможно ограничить количество шагов как функцию количества сторон многоугольника.
История
Пол Эрдёш предположил результат в 1935 году как проблему в Американский математический ежемесячный журнал. В версии, предложенной Эрдёшем, все карманы переворачиваются одновременно; однако это может привести к тому, что многоугольник станет непростым, поскольку два кармана могут переворачиваться друг на друга. В 1939 году Сёкефалви-Надь указал на эту проблему с помощью формулировки Эрдеша, переформулировал проблему в ее теперь стандартной форме и опубликовал доказательство. Доказательство Сёкефалви-Надя имело неверный случай, на что было указано в обзоре проблемы 1995 г. Бранко Грюнбаум; однако доказательства Грюнбаума и Годфрид Туссен так же неполны. Дополнительные доказательства (некоторые, но не все правильные) были предоставлены в 1957 году двумя независимыми российскими математиками Решетняком и Юсуповым, в 1959 году Бингом и Казариновым и в 1993 году Вегнером. Демейн, Гассенд, О'Рурк и Туссен исследуют эту историю. и предоставьте исправленное доказательство.
Вариации
Альтернативный метод выпуклых невыпуклых многоугольников, который также изучался, заключается в выполнении сальто, Поворот кармана на 180 градусов вокруг середины его выпуклой кромки корпуса.
Рекомендации
- Бранко Грюнбаум, Как сделать выпуклый многоугольник, Геомбинаторика, 5 (1995), 24–30.
- Годфрид Туссен, Теорема Эрдеша – Надя и ее разветвления., Proc. 11-я канадская конференция по вычислительной геометрии (1999), 219–236.
- Бранко Грюнбаум и Йозеф Закс, Выпуклость многоугольников переворотами и переворотами, Дискретная математика. 241 (2001), 333–342.
- E.D. Demaine, Б. Гассенд, Дж. О'Рурк, Г. Туссен, Все полигоны переворачиваются, верно? Обзоры по дискретной и вычислительной геометрии, 231–255, в Contemp. Математика., 453, амер. Математика. Соц., Провиденс, Род-Айленд, 2008.