Bodová triangulace - Point set triangulation

Dvě různé triangulace stejné sady 9 bodů v rovině.

A triangulace množiny bodů ${ displaystyle { mathcal {P}}}$ v Euklidovský prostor ${ displaystyle mathbb {R} ^ {d}}$ je zjednodušený komplex který pokrývá konvexní obal z ${ displaystyle { mathcal {P}}}$a jejichž vrcholy patří ${ displaystyle { mathcal {P}}}$.^[1] V letadlo (když ${ displaystyle { mathcal {P}}}$ je sada bodů v ${ displaystyle mathbb {R} ^ {2}}$), triangulace jsou tvořeny trojúhelníky spolu s jejich hranami a vrcholy. Někteří autoři vyžadují, aby všechny body ${ displaystyle { mathcal {P}}}$ jsou vrcholy jeho triangulací.^[2] V tomto případě triangulace sady bodů ${ displaystyle { mathcal {P}}}$ v rovině lze alternativně definovat jako maximální sadu nepřekračujících hran mezi body ${ displaystyle { mathcal {P}}}$. V rovině jsou triangulace zvláštními případy rovinné přímkové grafy.

Obzvláště zajímavým druhem triangulací jsou Delaunayovy triangulace. Jsou to geometrické duální z Voronoiovy diagramy. Delaunayova triangulace množiny bodů ${ displaystyle { mathcal {P}}}$ v rovině obsahuje Gabriel graf, graf nejbližšího souseda a minimální kostra z ${ displaystyle { mathcal {P}}}$.

Triangulace mají řadu aplikací a existuje zájem najít „dobré“ triangulace daného bodu stanovené pod určitými kritérii, jako například triangulace s minimální hmotností. Někdy je žádoucí mít triangulaci se speciálními vlastnostmi, např. Ve které mají všechny trojúhelníky velké úhly (jsou vyloučeny dlouhé a úzké trojúhelníky).^[3]

Vzhledem k sadě hran, které spojují body roviny, je problém určit, zda obsahují triangulaci NP-kompletní.^[4]

Pravidelné triangulace

Některé triangulace množiny bodů ${ displaystyle { mathcal {P}} podmnožina mathbb {R} ^ {d}}$ lze získat zvednutím bodů ${ displaystyle { mathcal {P}}}$ do ${ displaystyle mathbb {R} ^ {d + 1}}$ (což znamená přidat souřadnici ${ displaystyle x_ {d + 1}}$ do každého bodu ${ displaystyle { mathcal {P}}}$), výpočtem konvexního trupu zvednuté množiny bodů a promítnutím spodních ploch tohoto konvexního trupu zpět na ${ displaystyle mathbb {R} ^ {d}}$. Takto vytvořené triangulace se označují jako pravidelné triangulace z ${ displaystyle { mathcal {P}}}$. Když jsou body zvednuty k paraboloidu rovnice ${ displaystyle x_ {d + 1} = x_ {1} ^ {2} + cdots + x_ {d} ^ {2}}$, výsledkem této konstrukce je Delaunayova triangulace z ${ displaystyle { mathcal {P}}}$. Všimněte si, že aby tato konstrukce poskytla triangulaci, musí být spodní konvexní trup zvednuté sady bodů zjednodušující. V případě Delaunayových triangulací to vyžaduje požadavek, aby č ${ displaystyle d + 2}$ body ${ displaystyle { mathcal {P}}}$ ležet ve stejné sféře.

Kombinatorika v rovině

Každá triangulace libovolné množiny ${ displaystyle { mathcal {P}}}$ z ${ displaystyle n}$ body v rovině má ${ displaystyle 2n-h-2}$ trojúhelníky a ${ displaystyle 3n-h-3}$ hrany kde ${ displaystyle h}$ je počet bodů ${ displaystyle { mathcal {P}}}$ na hranici konvexní obal z ${ displaystyle { mathcal {P}}}$. To vyplývá z přímočarosti Eulerova charakteristika argument.^[5]

Algoritmy pro vytváření triangulací v rovině

Algoritmus rozdělení trojúhelníku : Najděte konvexní trup množiny bodů ${ displaystyle { mathcal {P}}}$ a triangulovat tento trup jako mnohoúhelník. Vyberte vnitřní bod a nakreslete hrany ke třem vrcholům trojúhelníku, který jej obsahuje. Pokračujte v tomto procesu, dokud nejsou vyčerpány všechny vnitřní body.^[6]

Inkrementální algoritmus : Seřadit body ${ displaystyle { mathcal {P}}}$ podle souřadnic x. První tři body určují trojúhelník. Zvažte další bod ${ displaystyle p}$ v objednané sadě a spojte ji se všemi dříve uvažovanými body ${ displaystyle {p_ {1}, ..., p_ {k} }}$ které jsou viditelné p. Pokračujte v tomto procesu přidávání jednoho bodu ${ displaystyle { mathcal {P}}}$ najednou až do všech ${ displaystyle { mathcal {P}}}$ bylo zpracováno.^[7]

Časová složitost různých algoritmů

Následující tabulka uvádí výsledky časové složitosti pro konstrukci triangulací množin bodů v rovině podle různých kritérií optimality, kde ${ displaystyle n}$ je počet bodů.

		minimalizovat	maximalizovat
minimální	úhel		${ displaystyle O (n log n)}$ (Delaunayova triangulace )
maximum		${ displaystyle O (n ^ {2} log n)}$ [8] [9]
minimální	plocha	${ displaystyle O (n ^ {2})}$ [10]	${ displaystyle O (n ^ {2} log n)}$ [11]
maximum		${ displaystyle O (n ^ {2} log n)}$ [11]
maximum	stupeň	NP-kompletní pro stupeň 7 [12]
maximum	excentricita	${ displaystyle O (n ^ {3})}$ [9]
minimální	délka hrany	${ displaystyle O (n log n)}$ (Nejbližší problém s dvojicí bodů )	NP-kompletní [13]
maximum		${ displaystyle O (n ^ {2})}$ [14]	${ displaystyle O (n log n)}$ (za použití Konvexní obal )
součet		NP-tvrdé (Triangulace s minimální hmotností )
minimální	výška		${ displaystyle O (n ^ {2} log n)}$ [9]
maximum	sklon	${ displaystyle O (n ^ {3})}$ [9]

Viz také

• Polygon triangulace

Poznámky

Reference