Erdős-Sökefalvi-Nagy-satsen
Erdős-Sökefalvi-Nagy-satsen är ett resultat i kombinatorisk geometri , enligt vilken en polygon utan självskärningar kan omvandlas till en konvex polygon genom ett ändligt antal spegelreflektioner av "fickor"-anslutna komponenter i det konvexa skrovet . Vid varje steg bestäms polygonens konvexa skrov och dess kant i förhållande till vilken reflektionen utförs. Den slutliga polygonen kan ha parallella intilliggande kanter, dvs vara något konvex . Förutom reflektion kan fickan förvandlas genom att den vrids 180° runt centrum av skalkanten. En sådan transformation visar sig vara ett mer effektivt sätt att uppnå polygonens konvexitet [1] .
Förmodan formulerades av Pal Erdős 1935 och publicerades i American Mathematical Monthly . År 1939 bevisade och publicerade Sökefalvi-Nagy satsen.
Sats
Vilken polygon som helst utan självkorsningar kan omvandlas till en svagt konvex polygon genom ett ändligt antal reflektioner av fickor från det konvexa skrovets kanter.
Historik
Satsen har en märklig historia och har upprepade gånger motbevisats. 1995 upptäckte Branko Grünbaum ett subtilt fel i originalbeviset, som han lyckades eliminera.
Variationer och generaliseringar
- Joss och Shannon bevisade att det erforderliga antalet reflektioner inte kan begränsas ens för fyrhörningar. De gav också poäng på antalet varv.
- Vilken -gon som helst utan självkorsningar kan omvandlas till en svagt konvex genom att bara rotera fickorna runt kanterna på det konvexa skrovet.
- Författarna till satsen antog att det faktiskt finns tillräckligt med rotationer [2] . Från och med 2013 är det inte bevisat.
- Grünbaum-Sachs teorem: Vilken polygon som helst kan göras svagt konvex genom ett ändligt antal fickrotationer runt det konvexa skrovets kanter.
- Vilken -gon som helst utan självkorsningar kan omvandlas till en svagt konvex genom att bara rotera fickorna runt kanterna på det konvexa skrovet.
Anteckningar
- ↑ Branko Grünbraum och Joseph Sachs. Konvexifiering av polygoner genom vändningar och genom vändningar // Diskret matematik. - 2001. - T. 241 . - S. 333-342 . Arkiverad från originalet den 30 maj 2013.
- ↑ Branko Grünbaum . Hur man konvexifierar en polygon // Geombinatorials . - 1995. - Nr 5 . - S. 24-30 .
Litteratur
- Godfried Toussaint . Erdős-Nagy-satsen och dess förgreningar // Proc. 11:e kanadensiska konferensen om beräkningsgeometri. - 1999. - S. 219-236 .
- E.D. Demaine , B. Gassend, J. O'Rourke, G.T. Toussaint. Alla polygoner vänder ändligt eller hur? Undersökningar om diskret och beräkningsgeometri // Contemp. Matematik. — Providence, R.I.: Amer. Matematik. Soc, 2008. - T. 453 . - S. 231-255 .