Triangulación de conjuntos de puntos

Triangulación de un conjunto de puntos${\displaystyle {\mathcal {P}}}$en el espacio euclidiano${\displaystyle \mathbb {R} ^{d}}$es un complejo simplicial que cubre la envoltura convexa de${\displaystyle {\mathcal {P}}}$y cuyos vértices pertenecen a${\displaystyle {\mathcal {P}}}$. ^{[ 1 ]} En el plano (cuando${\displaystyle {\mathcal {P}}}$es un conjunto de puntos en${\displaystyle \mathbb {R} ^{2}}$), las triangulaciones están formadas por triángulos, junto con sus aristas y vértices. Algunos autores requieren que todos los puntos de${\displaystyle {\mathcal {P}}}$son vértices de sus triangulaciones. ^{[ 2 ] [ 3 ]} En este caso, una triangulación de un conjunto de puntos${\displaystyle {\mathcal {P}}}$en el plano se puede definir alternativamente como un conjunto máximo de aristas que no se cruzan entre puntos de${\displaystyle {\mathcal {P}}}$. En el plano, las triangulaciones son casos especiales de grafos de líneas rectas planas . ^{[ 4 ]}

Las triangulaciones de Delaunay ^{[ 5 ]} son ​​las duales geométricas de los diagramas de Voronoi . La triangulación de Delaunay de un conjunto de puntos${\displaystyle {\mathcal {P}}}$en el plano contiene el grafo de Gabriel , el grafo del vecino más cercano y el árbol de expansión mínima de${\displaystyle {\mathcal {P}}}$. ^{[ 6 ]}

Las triangulaciones tienen diversas aplicaciones, y existe interés en encontrar las triangulaciones "óptimas" 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 ("astillados")). ^{[ 7 ]}

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

Algunas triangulaciones de un conjunto de puntos${\displaystyle {\mathcal {P}}\subset \mathbb {R} ^{d}}$se puede obtener levantando los puntos de${\displaystyle {\mathcal {P}}}$en${\displaystyle \mathbb {R} ^{d+1}}$(lo que equivale a añadir una coordenada)${\displaystyle x_{d+1}}$a cada punto de${\displaystyle {\mathcal {P}}}$), calculando la envoltura convexa del conjunto de puntos elevados y proyectando las caras inferiores de esta envoltura convexa de vuelta sobre${\displaystyle \mathbb {R} ^{d}}$Las triangulaciones construidas de esta manera se denominan triangulaciones regulares de${\displaystyle {\mathcal {P}}}$Cuando los puntos se elevan al paraboloide de la ecuación${\displaystyle x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}}$, esta construcción da como resultado la triangulación de Delaunay de${\displaystyle {\mathcal {P}}}$. 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 no${\displaystyle d+2}$puntos de${\displaystyle {\mathcal {P}}}$yacen en la misma esfera. ^{[ 9 ]}

Además de las triangulaciones clásicas de Delaunay y regulares, en geometría computacional se han estudiado otras formas y problemas relacionados con 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 , ^{[ 10 ]} 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. ^{[ 11 ]} 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. ^{[ 12 ]} Las triangulaciones de conjuntos de puntos también pueden verse como grafos de líneas rectas planares máximos, ya que no se pueden agregar aristas rectas adicionales sin destruir la planaridad. ^{[ 13 ]} 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. ^{[ 14 ]} Los avances en geometría combinatoria también han producido nuevos límites en el número de triangulaciones distintas realizables en un conjunto de puntos fijo, lo que resalta la complejidad exponencial de estas estructuras. ^{[ 15 ]}

Cada triangulación de cualquier conjunto${\displaystyle {\mathcal {P}}}$de${\displaystyle n}$puntos en el plano tiene${\displaystyle 2n-h-2}$triángulos y${\displaystyle 3n-h-3}$bordes donde${\displaystyle h}$es el número de puntos de${\displaystyle {\mathcal {P}}}$en el límite de la envoltura convexa de${\displaystyle {\mathcal {P}}}$Esto se deduce de un argumento sencillo basado en la característica de Euler . ^{[ 16 ]}

Algoritmo de división de triángulos  : Encontrar la envoltura convexa del conjunto de puntos.${\displaystyle {\mathcal {P}}}$y triangula este casco como un polígono. Elige un punto interior y dibuja aristas hasta los tres vértices del triángulo que lo contiene. Continúa este proceso hasta que se hayan utilizado todos los puntos interiores. ^{[ 17 ]}

Algoritmo incremental  : Ordenar los puntos de${\displaystyle {\mathcal {P}}}$Según las coordenadas x. Los tres primeros puntos determinan un triángulo. Consideremos el siguiente punto.${\displaystyle p}$en el conjunto ordenado y conectarlo con todos los puntos considerados previamente.${\displaystyle \{p_{1},...,p_{k}\}}$que son visibles para p.  Continúe este proceso de agregar un punto de${\displaystyle {\mathcal {P}}}$a la vez hasta que todos${\displaystyle {\mathcal {P}}}$ha sido procesado. ^{[ 18 ]}

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${\displaystyle n}$es el número de puntos.

• Generación de malla
• Triangulación de polígonos