Triangulation de Pitteway

Quand une triangulation de Pitteway existe, le milieu de chaque arête à l'intérieur de la triangulation doit avoir comme plus proches voisins les deux sommets de l'arête, car autrement la propriété de Pitteway serait violée pour les points proches de ce milieu dans l'un des deux triangles adjacents. Ainsi, un cercle ayant pour diamètre cette arête ne doit pas contenir de sommet, ce qui fait que la triangulation de Pitteway correspond au graphe de Gabriel augmenté de l'enveloppe convexe de l'ensemble de points. Réciproquement, quand un graphe de Gabriel et une enveloppe convexe forment une triangulation, c'est une triangulation de Pitteway.

Comme le graphe de Gabriel et l'enveloppe convexe sont des parties de la triangulation de Delaunay, cela signifie qu'une triangulation de Pitteway, lorsqu'elle existe, est unique pour un ensemble de points en position générale et coïncide avec la triangulation de Delaunay.

Dans une triangulation de Pitteway, chaque arête pq soit appartient à l'enveloppe convexe, soit coupe l'une des arêtes du diagramme de Voronoi séparant les cellules contenant les points p et q, c'est-à-dire le dual à la triangulation. Pour certaines sources, cette propriété est utilisée pour définir une triangulation de Pitteway comme une triangulation de Delaunay dans laquelle toutes les arêtes internes coupent leur arête duale dans le diagramme de Voronoi. Les arêtes externes peuvent ne pas couper leurs duales^[3].

• Triangulation d'un ensemble de points
• Graphe de Gabriel
• Triangulation de Delaunay

Dobrin, Adam (2005), Review of Properties and Variations of Voronoi Diagrams, Whitman College

• Portail de la géométrie
• Portail de l’informatique