Twierdzenie Erdősa-Nagya
Erdősa – Nagya jest wynikiem geometrii dyskretnej stwierdzającej, że niewypukły prosty wielokąt można przekształcić w wielokąt wypukły za pomocą skończonej sekwencji przewrotów. Odwrócenia są definiowane przez wzięcie wypukłej otoczki wielokąta i odbicie kieszeni w odniesieniu do krawędzi granicznej. Twierdzenie zostało nazwane na cześć matematyków Paula Erdősa i Béli Szőkefalvi-Nagy .
Oświadczenie
Kieszeń niewypukłego wielokąta prostego to wielokąt prosty ograniczony przez kolejny ciąg krawędzi wielokąta wraz z pojedynczą krawędzią jego wypukłej otoczki , która nie jest krawędzią samego wielokąta. Każda wypukła krawędź kadłuba, która nie jest krawędzią wielokąta, definiuje w ten sposób kieszeń. Odwrócenie kieszeni uzyskuje się poprzez odbicie krawędzi wielokąta, które ograniczają kieszeń, w poprzek linii odbicia zawierającej wypukłą krawędź kadłuba . Ponieważ odbita kieszeń leży całkowicie w odbitym obrazie wypukłej otoczki, po drugiej stronie tej prostej, ta operacja nie może wprowadzić żadnych przecięć, więc wynikiem odwrócenia jest kolejny prosty wielokąt o większym polu.
W niektórych przypadkach pojedyncze odwrócenie spowoduje, że niewypukły prosty wielokąt stanie się wypukły. Gdy to się stanie, nie będzie już możliwości wykonywania kolejnych przewrotów. Twierdzenie Erdősa – Nagya stwierdza, że zawsze można znaleźć sekwencję przewrotów, która w ten sposób tworzy wypukły wielokąt. Co więcej, dla każdego prostego wielokąta każda sekwencja przewrotów doprowadzi ostatecznie do powstania wielokąta wypukłego w skończonej liczbie kroków.
Istnieją czworoboki, które wymagają dowolnie dużej (ale skończonej) liczby przewrotów, aby stały się wypukłe. Dlatego nie jest możliwe ograniczenie liczby stopni jako funkcji liczby boków wielokąta.
Historia
Paul Erdős przypuścił wynik w 1935 roku jako problem w American Mathematical Monthly . W wersji przedstawionej przez Erdősa wszystkie kieszenie mają być odwracane jednocześnie; może to jednak spowodować, że wielokąt stanie się nieprosty, ponieważ dwie kieszenie mogą się nakładać na siebie. W 1939 roku Szőkefalvi-Nagy zwrócił uwagę na ten problem w sformułowaniu Erdősa, przeformułował problem w jego obecnie standardowej formie i opublikował dowód. Dowód Szőkefalvi-Nagy miał błędny przypadek, na co wskazano w badaniu problemu z 1995 r. Przeprowadzonym przez Branko Grünbauma ; jednak dowody Grünbauma i Godfrieda Toussainta są podobnie niekompletne. Dodatkowe dowody (niektóre, ale nie wszystkie poprawne) dostarczyli w 1957 r. dwaj niezależni matematycy rosyjscy, Reszetniak i Jusupow, w 1959 r. Bing i Kazarinow, aw 1993 r. Wegner. Demaine, Gassend, O'Rourke i Toussaint badają tę historię i przedstawiają poprawiony dowód.
Wariacje
Alternatywną metodą wypukłości niewypukłych wielokątów, która również została zbadana, jest wykonanie przewrotów , obrotów kieszeni o 180 stopni wokół środka jej wypukłej krawędzi kadłuba.
- Branko Grünbaum , Jak wypuklić wielokąt, Geombinatorics , 5 (1995), 24–30.
- Godfried Toussaint , Twierdzenie Erdősa-Nagya i jego konsekwencje , Proc. 11. kanadyjska konferencja na temat geometrii obliczeniowej (1999), 219–236.
- Branko Grünbaum i Joseph Zaks, Wypukłość wielokątów przez przerzucanie i odwracanie , Matematyka dyskretna. 241 (2001), 333–342.
- ED Demaine , B. Gassend, J. O'Rourke , GT Toussaint, Wszystkie wielokąty odwracają się w sposób skończony, prawda? Ankiety dotyczące geometrii dyskretnej i obliczeniowej , 231–255, w Contemp. Matematyka , 453, Am. Matematyka Soc., Providence, RI, 2008.