Triangulació d'un polígon

Triangulació d'un polígon

En geometria, la triangulació d'un polígon o àrea poligonal és una partició d'aquesta àrea en un conjunt de triangles.

De manera més precisa, una triangulació és una divisió de l'àrea en un conjunt de triangles que compleixen les següents condicions:

• La unió de tots els triangles és igual al polígon original.
• Els vèrtexs dels triangles són vèrtexs del polígon original.
• Qualsevol parella de triangles és disjunta o comparteix únicament un vèrtex o una banda.

La definició anterior és la estàndard en geometria computacional encara que en certs contextos, en parlar de triangulacions, es pot fer cas omís del segon requisit. En aquest cas, no es requereix que els vèrtexs dels triangles siguin vèrtexs del polígon i per referir-se a les triangulacions que sí que satisfan el requisit es parla de triangulacions completes .

La partició d'una superfície en triangles es denomina també malla triangular en trigonometria i en geometria elemental. I des del punt de vista de la teoria de grafs, les triangulacions són «grafs no orientats sense arestes múltiples», els subgrafs són "cercles de tres nodes" (i corresponentment tres arestes). Una generalització de les malles triangulars són les malles poligonals.

Triangulacions de polígons convexos

En el cas de polígons convex s, la quantitat de triangulacions possibles depèn únicament del nombre de costats del polígon. Representant per $t_{n}$ al nombre de triangulacions d'un polígon d' n costats, es compleix la següent relació de recurrència:

$t_{n}=t_{2}t_{n-1}+t_{3}t_{n-2}+\cdots +t_{n-1}t_{2}$,

la qual té per solució la fórmula

$t_{n}={\frac {1}{n-1}}{\binom {2n-4}{n-2}}$.

En altres paraules, s'estableix el següent teorema:

El nombre de particions d'un polígon convex de n costats és igual al ( n -2)-èsim nombre de Catalan, és a dir: $t_{n}=C_{n-2}={\frac {1}{n-1}}{\binom {2n-4}{n-2}}$.

Generalitzacions

Es defineix una triangulació d'un polítop en un espai de dimensió n com una conjunt de simplejos de dimensió n tals que:

• La unió de tots els simplejos és igual al polítop.
• Qualsevol parell de simplejos es disjunt o la seva intersecció és exactament alguna cara comú.

Triangulacions especials

Sovint interessa calcular una triangulació amb propietats especials. Per exemple, hi ha les triangulacions de Delaunay, que eviten els angulos aguts en els triangles, o les triangulacions de mínima ponderació ( Minimum-weight Triangulation ), en què es minimitza la longitud total de les arestes.

Vegeu també

• Triangulació de Delaunay