Triangulation de Pitteway

Le concept a été introduit par Michael Pitteway en 1973^[1]. McLain en parle aussi en 1976^[2]. Le nom "triangulation de Pitteway" date de Okabe et al., en 2000^[3].

Gold, en 1978^[4], fait remarquer que tous les ensembles de points n'admettent pas forcément de triangulation de Pitteway. Par exemple, n'importe quelle triangulation d'un pentagone régulier possède un triangle isocèle tel qu'un point p proche de milieu d'un des côtés du triangle isocèle sera plus proche d'un sommet en dehors du triangle que des sommets du triangle.

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].