Triangulación de Delaunay

La triangulación de Delaunay  es una triangulación para un conjunto dado de puntos S en un plano, en el que para cualquier triángulo todos los puntos de S , excepto los puntos que son sus vértices, se encuentran fuera del círculo descrito alrededor del triángulo. Denotado DT( S ) . Descrito por primera vez en 1934 por el matemático soviético Boris Delaunay .

Propiedades

• La triangulación de Delaunay corresponde uno a uno al diagrama de Voronoi para el mismo conjunto de puntos.
• Como corolario: si no hay cuatro puntos en el mismo círculo, la triangulación de Delaunay es única.
• La triangulación de Delaunay maximiza el ángulo mínimo entre todos los ángulos de todos los triángulos construidos, evitando así triángulos "delgados".
• La triangulación de Delaunay maximiza la suma de los radios de los círculos inscritos.
• La triangulación de Delaunay minimiza el funcional discreto de Dirichlet .
• La triangulación de Delaunay minimiza el radio máximo de la esfera envolvente mínima.
• La triangulación de Delaunay en el plano tiene la suma mínima de radios de círculos circunscritos a triángulos entre todas las triangulaciones posibles [1] .

Algoritmo divide y vencerás

Este algoritmo se basa en el método estándar para muchos algoritmos de reducir un problema complejo a otros más simples, en los que la solución es obvia. El algoritmo en sí consta de 2 pasos:

1. Dividir el conjunto original en conjuntos más pequeños. Para ello trazamos líneas verticales u horizontales en medio del conjunto y ya con respecto a estas líneas dividimos los puntos en dos partes aproximadamente a lo largo de . Después de eso, para cada grupo de puntos, comenzamos recursivamente el proceso de división.
2. Unión de triangulaciones óptimas. Primero, se encuentran dos pares de puntos, cuyos segmentos, junto con las triangulaciones construidas, forman una figura convexa. Están conectados por segmentos, y uno de los segmentos obtenidos se elige como el comienzo para el desvío posterior. El bypass es el siguiente: en este segmento, parece que "inflamos la burbuja" hacia adentro hasta el primer punto que alcanza el círculo de inflado de la "burbuja". El punto encontrado se conecta al punto del segmento que no estaba conectado a él. Se comprueba la intersección del segmento resultante con segmentos de triangulación ya existentes y, en caso de intersección, se eliminan de la triangulación. Después de eso, el nuevo segmento se toma como el comienzo de una nueva "burbuja". El ciclo se repite hasta que el comienzo coincide con el segundo segmento del casco convexo.

La complejidad de dividir el conjunto , unir - para cada unión, la complejidad final del algoritmo - [2] .

Variaciones y generalizaciones

• En el espacio tridimensional, es posible una construcción similar con círculos reemplazados por esferas.
• Las generalizaciones también se utilizan cuando se introducen métricas distintas de las euclidianas .
• Una de las propiedades de la triangulación de Delaunay, la suma mínima de radios de círculos circunscritos, se puede aplicar a la llamada triangulación restringida de Delaunay . Hay n puntos, algunas de las aristas de triangulación ya están dibujadas; dibujar el resto para que la suma de los radios de los círculos circunscritos sea la más pequeña.

Aplicación

Se garantiza que el árbol de expansión euclidiano mínimo está en una triangulación de Delaunay, por lo que algunos algoritmos usan triangulación. Además, mediante la triangulación de Delaunay , se resuelve aproximadamente el problema euclidiano del viajante de comercio .

En la interpolación 2D , la triangulación de Delaunay divide el plano en los triángulos más gruesos posibles, evitando ángulos demasiado agudos y demasiado obtusos. A partir de estos triángulos se puede construir, por ejemplo, interpolación bilineal .

El método de los elementos finitos  , un método para la solución numérica de ecuaciones diferenciales parciales, es extremadamente versátil y, con el crecimiento del poder de las computadoras y el desarrollo de bibliotecas estándar, se vuelve cada vez más popular. Sin embargo, la construcción de una malla de elementos finitos hasta hace poco seguía siendo un trabajo manual. En la mayoría de las variantes del método de elementos finitos, el error es inversamente proporcional al seno del ángulo de malla mínimo o máximo, por lo que muchos de los algoritmos de malla automática utilizan la triangulación de Delaunay.

Véase también

• Cuasitriangulación

Notas

1. ↑ Skvortsov, 2002 , teorema 3, p. once.
2. ↑ Skvortsov, 2002 , capítulo 3, algoritmo 3.1.

Literatura

• Triangulación de Skvortsov A. V. Delaunay y su aplicación . - Tomsk: Editorial de la Universidad de Tomsk, 2002. - 128 p. — ISBN 5-7511-1501-5 .
• Skvortsov A. V., Mirza N. S. Algoritmos para construir y analizar la triangulación . - Tomsk: Editorial de la Universidad de Tomsk, 2006. - 168 p. — ISBN 5-7511-2028-0 .