Analysis of longest-edge algorithms for 2-dimensional mesh refinement
Bedregal Lizárraga, Carlos Eduardo · 2015
Las tecnicas de generacion y refinamiento de mallas no estructuradas son usadas para la descomposicion de objetos geometricos. Estas tecnicas son muy utilizadas en areas como modelamiento geometrico, computacion grafica, computacion cientifica y aplicaciones de ingenieria, entre otras, lo que les da un interes interdisciplinario. Trabajando con triangulaciones (mallas compuestas por triangulos), el reto es generar una descomposicion precisa del objeto geometrico o dominio, y al mismo tiempo satisfacer las restricciones adicionales impuestas por la aplicacion, como restricciones en la forma de los elementos, el numero de elementos, o la transicion entre elementos de diferentes tamanos. Los algoritmos que ofrecen garantias teoricas sobre estos temas son preferidos. Los algoritmos de arista mas larga fueron disenados para el refinamiento iterativo de triangulaciones en aplicaciones de metodo de elementos finitos adaptativo. Estos algoritmos estan basados en la estrategia de propagacion por la arista mas larga. Comparados a otros algoritmos de refinamiento, los algoritmos de arista mas larga rapidamente producen una descomposicion del dominio (o de regiones de interes) a traves de operaciones locales simples. Las triangulaciones obtenidas presentan buena densidad y la calidad de los triangulos refinados esta acotada. El proposito de esta tesis es proporcionar nuevas garantias teoricas para los algoritmos de arista mas larga basados en biseccion y los algoritmos de arista mas larga basados en refinamiento Delaunay, para la generacion y el refinamiento de mallas de buena calidad en 2 dimensiones. Nuestro estudio del algoritmo basado en biseccion muestra que el algoritmo inserta un numero constante de puntos por triangulo refinado, con costo asintoticamente optimo. Tambien mostramos que durante el proceso de refinamiento el algoritmo mejora la calidad promedio de los triangulos. Obtenemos nuevas cotas para el tamano de la triangulacion refinada y probamos que este es a lo sumo un factor constante mayor que el tamano de la triangulacion inicial. Esta es la primera prueba completa sobre la complejidad del algoritmo. Seguidamente estudiamos el algoritmo basado en refinamiento Delaunay y su estrategia de insercion 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 triangulos para diversas cotas en el angulo minimo, y definimos las propiedades geometricas de los triangulos obtenidos despues del refinamiento. Utilizamos las tecnicas existentes para el analisis de algoritmos de refinamiento Delaunay para demostrar que el algoritmo produce triangulaciones de tamano optimo, con buena densidad de puntos, y con angulos internos entre 25.66 y 128.68 grados. Tambien estudiamos las propiedades de la propagacion en estos algoritmos de arista mas larga. Mostramos que el numero de triangulos afectados por refinamiento propagado converge rapidamente a…