Triangulación de Pitteway

En geometría computacional , una triangulación de Pitteway es una triangulación de conjuntos de puntos en la que el vecino más cercano de cualquier punto p dentro de la triangulación 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 del diagrama de Voronoi . 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 la envoltura convexa .

El concepto de triangulación de Pitteway fue introducido por Pitteway (1973) . Véase también McLain (1976) , quien escribe: «Una partición óptima es aquella en la que, para cualquier punto dentro de cualquier triángulo, ese punto se encuentra al menos tan cerca de uno de los vértices de ese triángulo como de cualquier otro punto de datos». El nombre «triangulación de Pitteway» fue acuñado por Okabe et al. (2000) .

Gold (1978) señala que no todos los conjuntos de puntos admiten una triangulación de Pitteway. Por ejemplo, cualquier triangulación de un pentágono regular 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 próximo fuera del triángulo.

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 dicha 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 el grafo de Gabriel junto con la envoltura convexa del conjunto de puntos. A la inversa, cuando el grafo de Gabriel y la envoltura convexa forman juntos una triangulación, se trata de una triangulación de Pitteway.

Dado que todas las aristas del grafo de Gabriel y de la envoltura convexa forman parte de la triangulación de Delaunay , una triangulación de Pitteway, cuando existe, es única para puntos en 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 pertenece a la envoltura convexa o cruza la arista del diagrama de Voronoi 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 envoltura convexa que no cruzan sus duales. ^{[ 1 ]}

• Dobrin, Adam (2005), Una revisión de las propiedades y variaciones de los diagramas de Voronoi (PDF) , Whitman College

• Gold, CM (1978), "Generación y uso práctico de estructuras de datos de elementos triangulares geográficos" (PDF) , en Dutton, G. (ed.), Actas del Primer Simposio Internacional de Estudios Avanzados sobre Estructuras de Datos Topológicas para Sistemas de Información Geográfica. Documentos de Harvard sobre Sistemas de Información Geográfica, vol. 5 — Estructuras de datos: superficiales y multidimensionales, Boston: Laboratorio de Gráficos por Computadora y Análisis Espacial, Universidad de Harvard, pp. 1–18 . .

• McLain, DH (1976), "Interpolación bidimensional a partir de datos aleatorios.", The Computer Journal , 19 (2): 178– 181, doi : 10.1093/comjnl/19.2.178.

• Okabe, Atsuyuki; Boots, Barry N.; Chiu, Sung Nok; Sugihara, Kokichi (2000), Teselaciones espaciales: conceptos y aplicaciones de los diagramas de Voronoi , Wiley.

• Pitteway, MLV (1973), "Investigación en gráficos por computadora en un entorno académico", Datafair '73.