Teorema celor două urechi

În geometrie teorema celor două urechi afirmă că fiecare poligon simplu cu mai mult de trei vârfuri are cel puțin două urechi, vârfuri care pot fi eliminate din poligon fără a introduce nicio intersectare. Teorema celor două urechi este echivalentă cu existența triangulării poligoanelor. Este adesea atribuită lui Gary H. Meisters, dar a fost demonstrată anterior de Max Dehn.

Enunțul teoremei

O ureche a unui poligon este definită ca fiind un vârf, $v$ , pentru care segmentul de dreaptă dintre vârfurile vecine lui $v$ se află în întregime în interiorul poligonului. Teorema celor două urechi afirmă că orice poligon simplu are cel puțin două urechi.

Urechi din triangulări

O ureche împreună cu cele două vârfuri vecine ale sale formează un triunghi în interiorul poligonului, care nu este traversat de nicio altă latură a poligonului. Eliminarea unui triunghi de acest tip produce un poligon cu mai puține laturi, iar eliminarea repetată a urechilor permite oricărui poligon simplu să fie triangulat.

Invers, dacă un poligon este triangulat, graful dual slab^⁠(d) al triangulării (un graf cu un nod pe triunghi și o muchie pe perechea de triunghiuri adiacente) va fi un arbore și fiecare nod terminal al arborelui va forma o ureche. Deoarece fiecare arbore cu mai mult de un nod are cel puțin două noduri terminale, fiecare poligon triangulat cu mai mult de un triunghi are cel puțin două urechi. Astfel, teorema celor două urechi este echivalentă cu faptul că fiecare poligon simplu are o triangulare.^[1]

Tipuri înrudite de vârfuri

Se spune despre o ureche că este expusă când formează un vârf al înfășurătoarei convexe a poligonului. Însă este posibil ca un poligon să nu aibă urechi expuse.^[2]

Urechile sunt un caz particular al unui vârf principal, un vârf la care segmentul de dreaptă care leagă vecinii vârfului nu traversează poligonul și nu atinge niciun alt vârf al acestuia. Un vârf principal pentru care acest segment de dreaptă se află în afara poligonului este numit gură. În mod analog cu teorema celor două urechi, fiecare poligon simplu neconvex are cel puțin o gură. Poligoanele cu numărul minim de vârfuri principale ale ambelor tipuri, două urechi și o gură, se numesc poligoane antropomorfe.^[3]

Istoric și demonstrație

Teorema celor două urechi este adesea atribuită unei lucrări din 1975 a lui Gary H. Meisters, din care provine terminologia ureche.^[4] Însă teorema a fost demonstrată anterior de Max Dehn (în circa 1899) ca parte a unei demonstrații a teoremei lui Jordan. Pentru a demonstra teorema, Dehn observă că fiecare poligon are cel puțin trei vârfuri convexe. Dacă unul dintre aceste vârfuri, $v$ , nu este o ureche, atunci poate fi conectat printr-o diagonală de un alt vârf $x$ în interiorul triunghiului $uvw$ format din $v$ și cei doi vecini ai săi; $x$ poate fi ales să fie vârful din acest triunghi care este cel mai îndepărtat de linia $uw$ . Această diagonală descompune poligonul în două poligoane mai mici, iar descompunerea repetată prin urechi și diagonale produce în cele din urmă o triangulare a întregului poligon, din care o ureche poate fi găsită ca un nod terminal al arborelui dual.^[5]

Note

^ en O'Rourke, Joseph (1987), Art Gallery Theorems and Algorithms, International Series of Monographs on Computer Science, Oxford University Press, ISBN 0-19-503965-3, MR 0921437
^ en Meisters, G. H. (1980), „Principal vertices, exposed points, and ears”, American Mathematical Monthly, 87 (4): 284–285, doi:10.2307/2321563, JSTOR 2321563, MR 0567710
^ Toussaint, Godfried (1991), „Anthropomorphic polygons”, American Mathematical Monthly, 98 (1): 31–35, doi:10.2307/2324033, JSTOR 2324033, MR 1083611
^ en Meisters, G. H. (1975), „Polygons have ears”, American Mathematical Monthly, 82 (6): 648–651, doi:10.2307/2319703, JSTOR 2319703, MR 0367792
^ en Guggenheimer, Heinrich (1977), „The Jordan curve theorem and an unpublished manuscript by Max Dehn” (PDF), Archive for History of Exact Sciences, 17 (2): 193–200, doi:10.1007/BF02464980, JSTOR 41133486, MR 0532231

Legături externe

en Meisters' Two Ears Theorem, la Cut-the-Knot
en The Two-Ears Theorem, Godfried Toussaint
en Eric W. Weisstein, Two-Ears Theorem la MathWorld.

Portal Matematică

[1] O'Rourke, Joseph (1987), Art Gallery Theorems and Algorithms, International Series of Monographs on Computer Science, Oxford University Press, ISBN 0-19-503965-3, MR 0921437

[2] Meisters, G. H. (1980), „Principal vertices, exposed points, and ears”, American Mathematical Monthly, 87 (4): 284–285, doi:10.2307/2321563, JSTOR 2321563, MR 0567710

[3] Toussaint, Godfried (1991), „Anthropomorphic polygons”, American Mathematical Monthly, 98 (1): 31–35, doi:10.2307/2324033, JSTOR 2324033, MR 1083611

[4] Meisters, G. H. (1975), „Polygons have ears”, American Mathematical Monthly, 82 (6): 648–651, doi:10.2307/2319703, JSTOR 2319703, MR 0367792

[5] Guggenheimer, Heinrich (1977), „The Jordan curve theorem and an unpublished manuscript by Max Dehn” (PDF), Archive for History of Exact Sciences, 17 (2): 193–200, doi:10.1007/BF02464980, JSTOR 41133486, MR 0532231

[1]

[2]

[3]

[4]

[5]