Věta o dvou uších - Two ears theorem - Wikipedia

Trojúhelníkový mnohoúhelník. Dva vrcholy na koncích řetězce trojúhelníků tvoří uši. Tento mnohoúhelník má však i další uši, které v této triangulaci nejsou patrné.

v geometrie, věta o dvou uších uvádí, že každý jednoduchý mnohoúhelník s více než třemi vrcholy má alespoň dva uši, vrcholy, které lze odstranit z mnohoúhelníku bez zavedení jakýchkoli křížení. Věta o dvou uších je ekvivalentní existenci polygonové triangulace. To je často přičítáno Gary H. Meisters, ale bylo prokázáno dříve Max Dehn.

Výrok věty

Ucho mnohoúhelníku je definováno jako vrchol proti tak, aby úsečka mezi dvěma sousedy proti leží zcela uvnitř polygonu. Věta o dvou uších uvádí, že každý jednoduchý mnohoúhelník má alespoň dvě uši.

Uši z triangulací

Ucho a jeho dva sousedé tvoří a trojúhelník uvnitř polygonu, který neprochází žádnou jinou částí polygonu. Odstranění trojúhelníku tohoto typu vytvoří mnohoúhelník s menším počtem stran a opakované odstraňování uší umožňuje existenci libovolného jednoduchého mnohoúhelníku trojúhelníkové.

Naopak, pokud je mnohoúhelník trojúhelníkový, je slabý duální triangulace (graf s jedním vrcholem na trojúhelník a jednou hranou na pár sousedních trojúhelníků) bude a strom a každý list stromu vytvoří ucho. Protože každý strom s více než jedním vrcholem má alespoň dva listy, má každý trojúhelníkový mnohoúhelník s více než jedním trojúhelníkem alespoň dvě uši. Věta o dvou uších je tedy ekvivalentní skutečnosti, že každý jednoduchý mnohoúhelník má triangulaci.[1]

Související typy vrcholů

Ucho se volá vystavena když tvoří vrchol konvexní obal mnohoúhelníku. Je však možné, že mnohoúhelník nemá žádné odkryté uši.[2]

Uši jsou zvláštním případem a hlavní vrchol, vrchol takový, že úsečka spojující sousedy vrcholů nepřekročí mnohoúhelník ani se nedotkne žádného jiného vrcholu. Hlavní vrchol, pro který tento úsečka leží mimo mnohoúhelník, se nazývá a ústa. Analogicky k teorému dvou uší má každý nekonvexní jednoduchý mnohoúhelník alespoň jedno ústo. Polygony s minimálním počtem hlavních vrcholů obou typů, dvěma ušima a ústy, se nazývají antropomorfní polygony.[3]

Historie a důkaz

Věta o dvou uších je často přičítána článku z roku 1975 Garyho H. Meisterse, z něhož pochází „ušní“ terminologie.[4] Věta však byla dříve prokázána Max Dehn (kolem roku 1899) jako součást dokladu o Jordanova věta o křivce. K prokázání věty Dehn poznamenává, že každý polygon má alespoň tři konvexní vrcholy. Pokud jeden z těchto vrcholů, proti„není ucho, může být spojeno úhlopříčkou s jiným vrcholem X uvnitř trojúhelníku uvw tvořil proti a jeho dva sousedé; X lze zvolit jako vrchol v tomto trojúhelníku, který je nejvzdálenější od čáry uw. Tato úhlopříčka rozloží polygon na dva menší polygony a opakovaný rozklad uši a úhlopříčkami nakonec vytvoří triangulaci celého polygonu, ze které lze ucho najít jako list dvojitého stromu.[5]

Reference

  1. ^ O'Rourke, Josephe (1987), Věty a algoritmy umělecké galerie, Mezinárodní série monografií o informatice, Oxford University Press, ISBN  0-19-503965-3, PAN  0921437.
  2. ^ Meisters, G. H. (1980), „Hlavní vrcholy, exponované body a uši“, Americký matematický měsíčník, 87 (4): 284–285, doi:10.2307/2321563, PAN  0567710.
  3. ^ Toussaint, Godfried (1991), "Anthropomorphic polygons", Americký matematický měsíčník, 98 (1): 31–35, doi:10.2307/2324033, PAN  1083611.
  4. ^ Meisters, G. H. (1975), „Mnohoúhelníky mají uši“, Americký matematický měsíčník, 82: 648–651, doi:10.2307/2319703, PAN  0367792.
  5. ^ Guggenheimer, H. (1977), „Věta Jordanovy křivky a nepublikovaný rukopis Maxe Dehna“ (PDF), Archiv pro historii přesných věd, 17 (2): 193–200, doi:10.1007 / BF02464980, JSTOR  41133486, PAN  0532231.

externí odkazy