Una triangulación de un conjunto de puntos en un espacio euclídeo es un complejo simplicial que cubre la envolvente convexa de , y cuyos vértices pertenecen a . En un plano (cuando es un conjunto de puntos en ), las triangulaciones están formadas por triángulos, junto con sus aristas y vértices. Algunos autores requieren que todos los puntos de sean vértices de sus triangulaciones. En este caso, una triangulación de un conjunto de puntos en el plano puede definirse alternativamente como un conjunto máximo de aristas que no se cruzan conectando puntos. En el plano, las triangulaciones son casos especiales de grafos de líneas rectas planos.

Las triangulaciones de Delaunay son los duales geométricos de los polígonos de Thiessen. La triangulación de Delaunay de un conjunto de puntos en el plano contiene el grafo de Gabriel, el grafo del vecino más cercano y el árbol recubridor mínimo de .

Las triangulaciones tienen diversas aplicaciones, y existe interés en encontrar las triangulaciones buenas de un conjunto de puntos dado bajo ciertos criterios, como por ejemplo las triangulaciones de peso mínimo. A veces es deseable tener una triangulación con propiedades especiales, por ejemplo, en la que todos los triángulos tengan ángulos grandes (se evitan los triángulos largos y estrechos).

Dado un conjunto de aristas que conectan puntos del plano, el problema de determinar si contienen una triangulación es NP-completo.

Triangulaciones regulares Algunas triangulaciones de un conjunto de puntos se pueden obtener elevando los puntos de a (lo que equivale a añadir una coordenada a cada punto de ), calculando la envolvente convexa del conjunto de puntos elevado y proyectando las caras inferiores de esta envolvente convexa sobre . Las triangulaciones construidas de esta manera se denominan triangulaciones regulares de . Cuando los puntos se elevan al paraboloide de la ecuación , esta construcción resulta en una triangulación de Delaunay de . Nótese que, para que esta construcción proporcione una triangulación, la envolvente convexa inferior del conjunto de puntos elevados debe ser simplicial. En el caso de las triangulaciones de Delaunay, esto equivale a exigir que ningún grupo de puntos de se encuentren en la misma esfera.

Variantes y extensiones Además de las triangulaciones clásicas de Delaunay y las triangulaciones regulares, se han estudiado en geometría computacional otras formas y problemas relacionados con las triangulaciones de conjuntos de puntos. La triangulación de peso mínimo (MWT) busca una triangulación de un conjunto de puntos que minimice la longitud total de las aristas. Aunque se ha demostrado que este problema es NP-difícil, se han desarrollado algoritmos de aproximación y heurísticas. Una heurística relacionada, la triangulación voraz, construye una triangulación añadiendo repetidamente la arista más corta que no interseca las aristas existentes, lo que produce buenas aproximaciones en la práctica. Otro tipo especial es la triangulación de Pitteway, en la que cada arista conecta un par de puntos cuyas celdas de Voronoi comparten un segmento de frontera. Estas triangulaciones están estrechamente relacionadas con los grafos de Delaunay y Gabriel. Las triangulaciones de conjuntos de puntos también pueden considerarse como grafos de líneas rectas planares máximos, ya que no se pueden añadir aristas rectas adicionales sin destruir la planaridad.Fáry, I. (1948). "On straight line representation of planar graphs". Acta Scientiarum Mathematicarum. 11: 229–233. Más recientemente, se han propuesto enfoques de aprendizaje automático para generar triangulaciones directamente a partir de nubes de puntos no estructuradas, como PointTriNet, que utiliza redes neuronales para aprender patrones de triangulación para datos 2D y 3D. Los avances en geometría combinatoria también han proporcionado nuevos límites al número de triangulaciones distintas realizables en un conjunto fijo de puntos, lo que pone de manifiesto la complejidad exponencial de estas estructuras.

Combinatoria en el plano Toda triangulación de cualquier conjunto de puntos en el plano tiene triángulos y aristas, donde es el número de puntos de en el límite de la envolvente convexa de . Esto se deduce directamente de la característica de Euler..

Algoritmos para construir triangulaciones en el plano Algoritmo de división de triángulos: Hallar la envolvente convexa del conjunto de puntos y triangular esta envolvente como un polígono. Elegir un punto interior y trazar aristas a los tres vértices del triángulo que lo contiene. Continuar este proceso hasta agotar todos los puntos interiores.Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 60.

Algoritmo incremental: Ordenar los puntos de según sus coordenadas x. Los tres primeros puntos determinan un triángulo. Considerar el siguiente punto en el conjunto ordenado y conectarlo con todos los demás puntos previamente considerados que son visibles para p. Continuar este proceso de agregar un punto de a la vez hasta que se haya procesado todo .Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 62.

Complejidad temporal de varios algoritmos La siguiente tabla muestra los resultados de complejidad temporal para la construcción de triangulaciones de conjuntos de puntos en el plano, bajo diferentes criterios de optimalidad, donde es el número de puntos.

Complejidad mínimaComplejidad máximamínimoángulo (triangulación de Delaunay)máximo mínimaárea máxima máximogradoNP-completo para grado 7 máximaexcentricidad mínimalongitud de arista (problema del par de puntos más cercanos)NP-completo máxima (utilizando la envolvente convexa)suma deNP-difícil (triangulación de peso mínimo)mínimaaltura máximapendiente

Véase también Generación de mallas Triangulación de un polígono

Referencias

Bibliografías

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