Erdős-Sökefalvi-Nagy Tétel
Az Erdős-Sökefalvi-Nagy tétel a kombinatorikus geometria eredménye , miszerint egy önmetszéspontok nélküli sokszög a konvex hajótest "zsebekkel" összefüggő komponenseinek véges számú tükörreflexiójával konvex sokszöggé alakítható . Minden lépésben meghatározzák a sokszög domború testét, és annak élét, amelyhez képest a visszaverődés történik. A végső sokszögnek lehetnek párhuzamos szomszédos élei, azaz lehet enyhén konvex . A reflexió mellett a zseb átalakítható, ha 180°-kal elforgatjuk a héj élének közepe körül. Egy ilyen transzformáció hatékonyabb eszköznek bizonyul a sokszög konvexitása elérésére [1] .
A sejtést Erdős Pál fogalmazta meg 1935-ben, és az American Mathematical Monthly -ban publikálta . 1939 - ben Sökefalvi-Nagy bebizonyította és publikálta a tételt.
Tétel
Bármely önmetszéspont nélküli sokszög átalakítható gyengén konvex sokszöggé a domború hajótest széleiről való véges számú zseb visszaverődésével.
Történelem
A tételnek furcsa története van, és többször is megcáfolták. 1995-ben Branko Grünbaum egy finom hibát fedezett fel az eredeti bizonyításban, amelyet sikerült kiküszöbölnie.
Változatok és általánosítások
- Joss és Shannon bebizonyította, hogy a szükséges reflexiók száma még négyszögeknél sem korlátozható. A fordulatok számát is pontozták.
- Bármely önmetszéspont nélküli -gon átalakítható gyengén domborúvá, csak a domború hajótest szélei körüli zsebek elforgatásával.
- A tétel szerzői azt feltételezték, hogy valójában elegendő forgás van [2] . 2013-ban még nem bizonyított.
- Grünbaum-Sachs tétel: Bármely sokszög gyengén domborúvá tehető a konvex hajótest élei körüli véges számú zsebelforgatással.
- Bármely önmetszéspont nélküli -gon átalakítható gyengén domborúvá, csak a domború hajótest szélei körüli zsebek elforgatásával.
Jegyzetek
- ↑ Branko Grünbraum és Joseph Sachs. Sokszögek konvexítése átfordításokkal és flipturnokkal // Discrete Math. - 2001. - T. 241 . - S. 333-342 . Az eredetiből archiválva : 2013. május 30.
- ↑ Branko Grünbaum . Sokszög konvexizálása // Geombinatorials . - 1995. - 5. sz . - S. 24-30 .
Irodalom
- Godfried Toussaint . Az Erdős-Nagy-tétel és elágazásai // Proc. 11. Kanadai Számítógépes Geometriai Konferencia. - 1999. - S. 219-236 .
- E. D. Demaine , B. Gassend, J. O'Rourke, G. T. Toussaint. Minden sokszög végesen átfordul, igaz? Felmérések a diszkrét és számítási geometriáról // Contemp. Math. - Providence, R.I.: Amer. Math. Szoc, 2008. - T. 453 . - S. 231-255 .