Analysis of longest-edge algorithms for 2-dimensional mesh refinement

Abstract

Las técnicas de generación y refinamiento de mallas no estructuradas son usadas para la descomposición de objetos geométricos. Estas técnicas son muy utilizadas en áreas como modelamiento geométrico, computación gráfica, computación científica y aplicaciones de ingeniería, entre otras, lo que les da un interés interdisciplinario. Trabajando con triangulaciones (mallas compuestas por triángulos), el reto es generar una descomposición precisa del objeto geométrico o dominio, y al mismo tiempo satisfacer las restricciones adicionales impuestas por la aplicación, como restricciones en la forma de los elementos, el número de elementos, o la transición entre elementos de diferentes tamaños. Los algoritmos que ofrecen garantías teóricas sobre estos temas son preferidos. Los algoritmos de arista más larga fueron diseñados para el refinamiento iterativo de triangulaciones en aplicaciones de método de elementos finitos adaptativo. Estos algoritmos están basados en la estrategia de propagación por la arista más larga. Comparados a otros algoritmos de refinamiento, los algoritmos de arista más larga rápidamente producen una descomposición del dominio (o de regiones de interés) a través de operaciones locales simples. Las triangulaciones obtenidas presentan buena densidad y la calidad de los triángulos refinados está acotada. El propósito de esta tesis es proporcionar nuevas garantías teóricas para los algoritmos de arista más larga basados en bisección y los algoritmos de arista más larga basados en refinamiento Delaunay, para la generación y el refinamiento de mallas de buena calidad en 2 dimensiones. Nuestro estudio del algoritmo basado en bisección muestra que el algoritmo inserta un número constante de puntos por triángulo refinado, con costo asintóticamente óptimo. También mostramos que durante el proceso de refinamiento el algoritmo mejora la calidad promedio de los triángulos. Obtenemos nuevas cotas para el tamaño de la triangulación refinada y probamos que éste es a lo sumo un factor constante mayor que el tamaño de la triangulación inicial. Esta es la primera prueba completa sobre la complejidad del algoritmo. Seguidamente estudiamos el algoritmo basado en refinamiento Delaunay y su estrategia de inserción de puntos. Demostramos que los puntos insertados por el algoritmo no pueden estar arbitrariamente cerca de puntos existentes, lo que nos permite acotar la longitud de nuevas aristas. Analizamos el mejoramiento de la calidad de triángulos para diversas cotas en el ángulo mínimo, y definimos las propiedades geométricas de los triángulos obtenidos después del refinamiento. Utilizamos las técnicas existentes para el análisis de algoritmos de refinamiento Delaunay para demostrar que el algoritmo produce triangulaciones de tamaño óptimo, con buena densidad de puntos, y con ángulos internos entre 25.66 y 128.68 grados. También estudiamos las propiedades de la propagación en estos algoritmos de arista más larga. Mostramos que el número de triángulos afectados por refinamiento propagado converge rápidamente a aproximadamente dos. Esto demuestra que el refinamiento propagado representa un factor constante en el costo de refinamiento.