En geometría computacional, una triangulación de Pitteway es un tipo de triangulación de conjuntos de puntos en la que el vecino más cercano de cualquier punto p dentro de la triangulación siempre es uno de los vértices del triángulo que contiene a p.

Alternativamente, es una triangulación de Delaunay en la que cada arista interna cruza su arista dual perteneciente a los polígonos de Thiessen. Las triangulaciones de Pitteway reciben su nombre de Michael Pitteway, quien las estudió en 1973. No todos los conjuntos de puntos admiten una triangulación de Pitteway. Cuando existe tal triangulación, es un caso especial de la triangulación de Delaunay y consiste en la unión del grafo de Gabriel y de la envolvente convexa.

Historia El concepto de triangulación de Pitteway fue introducido por . Véase también , quien escribió: Una partición óptima es aquella en la que, para cualquier punto dentro de cualquier triángulo, dicho punto se encuentra al menos tan cerca de uno de los vértices de ese triángulo como de cualquier otro punto del conjunto de datos. El nombre de triangulación de Pitteway fue acuñado por .

Contraejemplos señaló que no todo conjunto de puntos admite una triangulación de Pitteway. Por ejemplo, cualquier triangulación de un pentágono incluye un triángulo isósceles central tal que un punto p cercano al punto medio de uno de los lados del triángulo tiene su vecino más cercano fuera del triángulo.

Relación con otros grafos geométricos Cuando existe una triangulación de Pitteway, el punto medio de cada arista interior a la triangulación debe tener como vecinos más cercanos los dos extremos de la arista, ya que cualquier otro vecino violaría la propiedad de Pitteway para puntos cercanos en uno de los dos triángulos adyacentes. Por lo tanto, un círculo cuyo diámetro sea esa arista debe estar vacío de vértices, de modo que la triangulación de Pitteway consiste en un grafo de Gabriel junto con la envolvente convexa del conjunto de puntos. En sentido contrario, cuando el grafo de Gabriel y la envolvente convexa forman una triangulación, se trata de una triangulación de Pitteway.

Dado que todas las aristas del grafo de Gabriel y de la envolvente convexa forman parte del conjunto de la triangulación de Delaunay, una triangulación de Pitteway, cuando existe, es única para los puntos del conjunto en una posición general, y coincide con la triangulación de Delaunay. Sin embargo, los conjuntos de puntos sin triangulación de Pitteway seguirán teniendo una triangulación de Delaunay.

En la triangulación de Pitteway, cada arista pq perteneciente a la envolvente convexa o cruza la correspondiente arista del conjunto de polígonos de Thiessen que separa las celdas que contienen p y q. En algunas referencias, esta propiedad se utiliza para definir una triangulación de Pitteway, como una triangulación de Delaunay en la que todas las aristas internas de Delaunay cruzan sus aristas duales de Voronoi. Sin embargo, una triangulación de Pitteway puede incluir aristas de la envolvente convexa que no cruzan sus duales.; .

Referencias

Bibliografía

Categoría:Triangulación (geometría)