Teorema Erdős-Sökefalvi-Nagy
Teorema Erdős-Sökefalvi-Nagy este un rezultat al geometriei combinatorii , conform căruia un poligon fără auto-intersecții poate fi transformat într-un poligon convex printr-un număr finit de reflexii în oglindă ale „buzunarelor” - componentele conectate ale carcasei convexe . La fiecare pas, se determină carcasa convexă a poligonului și marginea acestuia, în raport cu care se efectuează reflexia. Poligonul final poate avea margini adiacente paralele, adică să fie ușor convex . Pe lângă reflexie, buzunarul poate fi transformat prin rotirea lui cu 180° în jurul centrului marginii carcasei. O astfel de transformare se dovedește a fi un mijloc mai eficient de realizare a convexității poligonului [1] .
Conjectura a fost formulată de Pal Erdős în 1935 și publicată în American Mathematical Monthly . În 1939 Sökefalvi-Nagy a demonstrat și a publicat teorema.
Teorema
Orice poligon fără auto-intersecții poate fi transformat într-un poligon slab convex printr-un număr finit de reflexii ale buzunarelor de la marginile carcasei convexe.
Istorie
Teorema are o istorie curioasă și a fost reproșată în mod repetat. În 1995, Branko Grünbaum a descoperit o eroare subtilă în dovada originală, pe care a reușit să o elimine.
Variații și generalizări
- Joss și Shannon au demonstrat că numărul necesar de reflexii nu poate fi limitat nici măcar pentru patrulatere. Au dat și un punctaj la numărul de ture.
- Orice -gon fără auto-intersecții poate fi transformat într-unul slab convex doar prin rotirea buzunarelor în jurul marginilor carcasei convexe.
- Autorii teoremei au emis ipoteza că de fapt există suficiente rotații [2] . Din 2013, nu a fost dovedit.
- Teorema Grünbaum-Sachs: Orice poligon poate fi făcut slab convex printr-un număr finit de rotații ale buzunarului în jurul marginilor carcasei convexe.
- Orice -gon fără auto-intersecții poate fi transformat într-unul slab convex doar prin rotirea buzunarelor în jurul marginilor carcasei convexe.
Note
- ↑ Branko Grünbraum și Joseph Sachs. Convexificarea poligoanelor prin flip-uri și prin flipturns // Matematică discretă. - 2001. - T. 241 . - S. 333-342 . Arhivat din original pe 30 mai 2013.
- ↑ Branko Grünbaum . Cum se convexează un poligon // Geombinatoriale . - 1995. - Nr 5 . - S. 24-30 .
Literatură
- Godfried Toussaint . Teorema Erdős-Nagy și ramificațiile sale // Proc. A 11-a Conferință canadiană de geometrie computațională. - 1999. - S. 219-236 .
- E. D. Demaine , B. Gassend, J. O'Rourke, G. T. Toussaint. Toate poligoanele se răstoarnă finit, nu? Studii privind geometria discretă și computațională // Contemp. Matematică. — Providence, R.I.: Amer. Matematică. Soc, 2008. - T. 453 . - S. 231-255 .