Erdős-Sökefalvi-Nagy-sætning

Erdős-Sökefalvi-Nagy-sætningen er et resultat i kombinatorisk geometri , ifølge hvilken en polygon uden selvskæringer kan omdannes til en konveks polygon ved et begrænset antal spejlrefleksioner af "lommer"-forbundne komponenter i det konvekse skrog . Ved hvert trin bestemmes polygonens konvekse skrog og dens kant, i forhold til hvilken refleksionen udføres. Den endelige polygon kan have parallelle tilstødende kanter, dvs. være let konveks . Ud over refleksion kan lommen transformeres ved at dreje den 180° omkring midten af skalkanten. En sådan transformation viser sig at være et mere effektivt middel til at opnå polygonens konveksitet [1] .

Formodningen blev formuleret af Pal Erdős i 1935 og offentliggjort i American Mathematical Monthly . I 1939 beviste och publicerede Sökefalvi-Nagy teoremet.

Sætning

Enhver polygon uden selvskæringer kan omdannes til en svagt konveks polygon ved et begrænset antal refleksioner af lommer fra kanterne af det konvekse skrog.

Historie

Sætningen har en mærkelig historie og er gentagne gange blevet irettesat. I 1995 opdagede Branko Grünbaum en subtil fejl i det originale bevis, som han formåede at eliminere.

Variationer og generaliseringer

Joss og Shannon beviste, at det nødvendige antal refleksioner ikke kan begrænses selv for firkanter. De gav også en score på antallet af vendinger.
- Enhver -gon uden selvkrydsninger kan omdannes til en svagt konveks en ved kun at dreje lommerne rundt om kanterne af det konvekse skrog. $n$ $(n-1)!$
  - Forfatterne af sætningen antog, at der faktisk er nok rotationer [2] . Fra 2013 er det ikke bevist. ${\frac {1}{4}}n^{2}$
- Grünbaum-Sachs sætning: Enhver polygon kan gøres svagt konveks ved et begrænset antal lommerotationer omkring kanterne af det konvekse skrog.

Noter

↑ Branko Grünbraum og Joseph Sachs. Konveksificering af polygoner ved flip og flipturns // Diskret matematik. - 2001. - T. 241 . - S. 333-342 . Arkiveret fra originalen den 30. maj 2013.
↑ Branko Grünbaum . Sådan konveksificerer man en polygon // Geombinatorials . - 1995. - Nr. 5 . - S. 24-30 .

Litteratur

Godfried Toussaint . Erdős-Nagy-sætningen og dens forgreninger // Proc. 11. canadisk konference om beregningsgeometri. - 1999. - S. 219-236 .
E. D. Demaine , B. Gassend, J. O'Rourke, G. T. Toussaint. Alle polygoner vender endeligt ikke? Undersøgelser om diskret og beregningsmæssig geometri // Contemp. Matematik. — Providence, R.I.: Amer. Matematik. Soc, 2008. - T. 453 . - S. 231-255 .