UNIVERSIDAD DE CHILE

FACULTAD DE CIENCIAS FÍSICAS Y MATEMÁTICAS DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

ESTUDIO DEL REFINAMIENTO DE MALLAS GEOMÉTRICAS DE TRIÁNGULOS RECTÁNGULOS ISÓSCELES

TESIS PARA OPTAR AL GRADO DE MAGÍSTER EN CIENCIAS MENCIÓN COMPUTACIÓN

OLIVER AMADEO VILCA HUAYTA

PROFESOR GUÍA: MARÍA CECILIA RIVARA ZÚÑIGA MIEMBROS DE LA COMISIÓN: NANCY VIOLA HITSCHFELD KAHLER CLAUDIO DOMINGO GUTIERREZ GALLARDO DIEGO JAVIER CELENTANO

SANTIAGO DE CHILE MARZO 2009

RESUMEN La tesis se sitúa en el área de las mallas geométricas, específicamente en el estudio del proceso de refinamiento y mejoramiento de las mismas, para estos fines, se ha diseñado y utilizado el algoritmo Lepp-Bisección basado en la bisección de triángulos por la arista más larga. El problema de refinamiento de mallas compuestas de triángulos rectángulos isósceles es: Dada una triangulación uniforme inicial Mi de triángulos rectángulos isósceles, una región de refinamiento R de Mi y un parámetro de longitud de arista ; obtener una triangulación refinada1 y conforme Mf de triángulos rectángulos isósceles, tal que la longitud de la arista más larga de cada triángulo de Mf que intersecta R sea menor o igual que . Se demostró que el refinamiento de la región R depende de la condición de refinamiento: En el refinamiento alrededor de un vértice P , la inserción de puntos y generación de triángulos es una función logarítmica de L . En el refinamiento alrededor de una arista (segmento) AB, la inserción de puntos y generación de triángulos es una función lineal de L . La inserción de puntos y generación de triángulos para el refinamiento de un sector cuadrado es una función cuadrática de L . Donde L es la longitud inicial de la arista más larga de los triángulos que intersectan R y  es la cota de la longitud de arista más larga a la cual se deben reducir todos los triángulos que intersectan R. Si el refinamiento es sobre una malla general TRI, hay la posibilidad del peor caso de refinamiento. Por lo que en el costo se debe agregar O(N). Donde N es el número total de triángulos de Mi . También se efectuó un estudio teórico y empírico sobre la longitud de propagación del LEPP, en el primero se calculó la longitud media de propagación del LEPP utilizando funciones generatrices de probabilidad, siendo ésta igual a cuatro triángulos. En el estudio empírico se experimentó para diferentes tamaños de muestras de vértices aleatorios. Para cada muestra se construyó la triangulación Delaunay y se obtuvo el promedio de las longitudes de propagación LEPP de los triángulos (que se conforman al expandir cada triángulo por la arista más larga). Los resultados empíricos concuerdan con los teóricos, la longitud media de propagación del LEPP es menor que cuatro (µ = 3,582) triángulos con una desviación estándar σ = 1,617 para muestras aleatorias mayores a mil vértices. 1

Insertando puntos y generando nuevos triángulos rectángulos isósceles por efecto de la bisección iterativa de los mismos. I

A Dios, quien me ha protegido. A mis padres que me han cuidado, a mi hermano Alfredo con quien compartí la misma infancia. A todos mis familiares, amigos y profesores.

II

Agradecimientos En primer lugar le agradezco mi madre Noemí, mujer esforzada que dio mucho por sus hijos, a mi padre Cristín. A mis hermanos Alfredo, Delma y Edwin. Debo reconocimiento a los profesores que me enseñaron, Ricardo Baeza, Sergio Ochoa, Alejandro Bassi, Claudio Gutiérrez, Gonzalo Navarro, Eric Tanter, María Cecilia Bastarrica, Rodrigo Paredes, Luis A. Guerrero, Marco Zúñiga, Cesar Guerrero, Sebastián Castro y al profesor José Pino quien me apoyó y me recibió atentamente cuando ingrese al programa de Postgrado. Agradezco el haber tenido buenos profesores. A todos los trabajadores administrativos de la Facultad de Ciencias Físicas Matemáticas de la Universidad de Chile, en especial a Angélica Aguirre, gracias por tu orientación, a Magaly Zúñiga, y a todo el personal del DCC sin excepción. En general a la Universidad de Chile y a la Escuela de Postgrado por su generosidad y por la oportunidad que me otorgó. Recibí conocimiento y también formación personal. También a mis compañeros y amigos en el DCC: Nayer Tumi, Andrés Neyem, Mauro San Martin, Renzo Angles, Diego Arroyuelo, Cristian Aracena, José Canuman, Javier Bustos, Francisco Venegas, Rodrigo González, Francisco Claude, Ricardo Barrientos, Lai Chun-Hau y Alcides Quispe. A los profesores de mi comisión, Claudio Gutiérrez, Nancy Hitschfeld, Diego Celentano. Finalmente, a mi profesora guía María Cecilia Rivara, muchas gracias por tu apoyo, comprensión y tiempo. Agradezco a todos ustedes por haber llegado a mi vida, no los olvidaré. Muchas gracias que Dios los bendiga.

III

Índice RESUMEN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Introducción 1.1. Aspectos generales . . . . . . . . . . . . . . . . . . . . . 1.2. Definición del problema . . . . . . . . . . . . . . . . . . . 1.2.1. El problema del refinamiento de triangulaciones 1.3. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1. Objetivo general . . . . . . . . . . . . . . . . . . . 1.3.2. Objetivos específicos . . . . . . . . . . . . . . . . 1.4. Metodología . . . . . . . . . . . . . . . . . . . . . . . . . 1.5. Descripción de los Contenidos . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

I

1 1 2 3 4 4 4 4 6

2. Antecedentes 7 2.1. Mallas de triángulos . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2. Refinamiento de triangulaciones mediante la bisección de triángulos 9 2.2.1. Bisección de un triángulo por la arista más larga . . . . . . . 9 2.2.2. Propiedades de la bisección de un triángulo por la arista más larga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.3. LEPP (Longest-Edge Propagation Path) . . . . . . . . . . . . 11 2.2.4. Algoritmo de refinamiento de triangulaciones (Lepp-bisección) 12 2.3. Refinamiento de mallas Delaunay . . . . . . . . . . . . . . . . . . . 13 3. Refinamiento de mallas de triángulos rectángulos isósceles 3.1. El problema de refinamiento de triángulos rectángulos isósceles . . 3.2. Triangulación uniforme TRI . . . . . . . . . . . . . . . . . . . . . . . 3.3. Refinamiento alrededor de un vértice . . . . . . . . . . . . . . . . . . 3.3.1. Refinamiento alrededor de un vértice para una triangulación TRI de cuatro triángulos (figura 3.6(a)) . . . . . . . . . . 3.3.2. Algoritmo para el refinamiento alrededor de un vértice . . . 3.3.3. Refinamiento alrededor de un vértice para una triangulación uniforme TRI . . . . . . . . . . . . . . . . . . . . . . . . . 3.4. Refinamiento alrededor de una arista . . . . . . . . . . . . . . . . . IV

16 16 19 21 21 26 27 28

3.5.

3.6.

3.7. 3.8.

3.4.1. Refinamiento alrededor de una arista para la triangulación TRI de la figura 3.8.(b) . . . . . . . . . . . . . . . . . . . . . . 3.4.2. Algoritmo para el refinamiento alrededor de una arista . . . 3.4.3. Refinamiento alrededor de una arista para una triangulación uniforme TRI . . . . . . . . . . . . . . . . . . . . . . . . . Refinamiento de un sector cuadrado . . . . . . . . . . . . . . . . . . 3.5.1. Refinamiento de un sector cuadrado para una triangulación TRI de la figura 3.10 . . . . . . . . . . . . . . . . . . . . . . . 3.5.2. Refinamiento de un sector cuadrado para una triangulación uniforme TRI . . . . . . . . . . . . . . . . . . . . . . . . . . . Refinamiento de un sector circular . . . . . . . . . . . . . . . . . . . 3.6.1. Refinamiento de un sector circular para la triangulación TRI de la figura 3.13 . . . . . . . . . . . . . . . . . . . . . . . 3.6.2. Refinamiento de un sector circular para una triangulación uniforme TRI . . . . . . . . . . . . . . . . . . . . . . . . . . . El peor caso de refinamiento de las triangulaciones generales TRI . Refinamiento en una triangulación general TRI . . . . . . . . . . .

28 35 37 37 37 47 47 47 49 50 51

4. Estadística experimental de la longitud de propagación del LEPP 4.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Peor caso de la longitud máxima de propagación LEPP en una malla 4.3. Longitud de propagación del LEPP en una malla Delaunay . . . . . 4.3.1. Longitud media de propagación del LEPP en una malla Delaunay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2. Longitud máxima de propagación del LEPP en una malla Delaunay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4. Longitud de propagación del LEPP en una malla refinada con Lepp-Delaunay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1. Longitud media de propagación del LEPP en una malla refinada con Lepp-Delaunay . . . . . . . . . . . . . . . . . . . . 4.4.2. Longitud máxima de propagación del LEPP en una malla refinada con Lepp-Delaunay . . . . . . . . . . . . . . . . . . . 4.5. Nuevo algoritmo de refinamiento: Lepp-Bisección-Delimitado . . .

52 52 53 54

5. Estadística teórica de la longitud de propagación del LEPP 5.1. Introducción a las funciones generatrices . . . . . . . . . . . . . . . 5.2. Función generatriz de probabilidad . . . . . . . . . . . . . . . . . . . 5.3. Longitud media de propagación del LEPP . . . . . . . . . . . . . . . 5.4. Desviación estándar de la longitud media de propagación del LEPP 5.5. Comparación de los resultados empíricos y teóricos de la longitud media de propagación del LEPP . . . . . . . . . . . . . . . . . . . . .

64 64 65 67 70

V

54 57 58 59 61 62

70

5.6. Cuando en el LEPP las probabilidades de tener un triángulo vecino de tipo A, B y C son distintas . . . . . . . . . . . . . . . . . . . . . . 71 6. Conclusiones

75

Bibliografía

79

VI

Índice de figuras 2.1. Bisección del triángulo ABC por la arista más larga. . . . . . . . . 10 2.2. Refinamiento LEPP del triángulo t0 . . . . . . . . . . . . . . . . . . . 12 3.1. Bisección de un triángulo rectángulo isósceles. . . . . . . . . . . . . 17 3.2. Bisección de un triángulo rectángulo escaleno. . . . . . . . . . . . . 17 3.3. Triangulación Delaunay compuesta por triángulos rectángulos (isósceles o no isósceles). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4. Inserción de un vértice en el circuncentro de un triángulo rectángulo isósceles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.5. Malla de triángulos rectángulos isósceles. . . . . . . . . . . . . . . . 19 3.6. Refinamiento alrededor de un vértice P . . . . . . . . . . . . . . . . 22 3.7. Iteraciones del refinamiento alrededor del vértice P . . . . . . . . . . 23 3.8. Refinamiento alrededor de una arista. . . . . . . . . . . . . . . . . . 30 3.9. Iteraciones del refinamiento alrededor de la arista AB. . . . . . . . 31 3.10.Refinamiento de un sector cuadrado ABCD. . . . . . . . . . . . . . . 39 3.11.Refinamiento dentro del área de un sector cuadrado Ω. . . . . . . . 40 3.12.Refinamiento en el exterior de un sector cuadrado. . . . . . . . . . . 44 3.13.Refinamiento de un sector circular. . . . . . . . . . . . . . . . . . . . 48 3.14.Peor caso del refinamiento de triángulos rectángulos isósceles. . . . 51 4.1. Peor caso de la longitud máxima de propagación LEPP en una malla (con n + 1 triángulos). . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Longitud media de propagación del LEPP en una malla Delaunay. 4.3. Longitud media de propagación del LEPP en una malla Delaunay. 4.4. Longitud del LEPP máximo en una malla Delaunay. . . . . . . . . . 4.5. Longitud media de propagación del LEPP en una malla refinada con Lepp-Delaunay. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6. Longitud media de propagación del LEPP en una malla refinada con Lepp-Delaunay. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7. Longitud del LEPP máximo en una malla refinada con LeppDelaunay. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

VII

54 55 57 58 59 60 61

Índice de Tablas 3.1. Vértices y triángulos insertados en el refinamiento alrededor de un vértice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Vértices insertados en el refinamiento alrededor de una arista. . . 3.3. Triángulos insertados en el refinamiento alrededor de una arista. . 3.4. Refinamiento por iteraciones dentro del área de un sector cuadrado. 3.5. Refinamiento por iteraciones en el exterior de un sector cuadrado. .

24 32 34 41 43

4.1. Resultados de los experimentos realizados sobre mallas construidas por puntos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.1. Resultados de la longitud media y desviación estándar de la propagación del LEPP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

VIII

Capítulo 1 Introducción

1.1.

Aspectos generales

Existen diferentes aplicaciones que utilizan triangulaciones en dos y tres dimensiones, por ejemplo, para el análisis de fenómenos físicos en ingeniería, modelación de terrenos, aplicaciones médicas, aplicaciones CAD/CAM1 , visualización científica, aplicaciones de computación gráfica, etc. En general se utilizan para describir objetos geométricos. En consideración a la amplia utilización de las mallas geométricas el refinamiento se ha convertido en una tarea necesaria para diferentes aplicaciones, en particular en el uso de métodos de elementos finitos adaptativos para analizar fenómenos físicos modelados por ecuaciones diferenciales parciales. Debido a este requerimiento y a su importancia en diferentes aplicaciones, el refinamiento de triangulaciones es objeto de estudio. 1

CAD: Computer-Aided Design. CAM: Computer-Aided Manufacturing.

1

Para el refinamiento de mallas, se ha diseñado diferentes estrategias, por ejemplo, las que se basan en la inserción de vértices en el circuncírculo de los triángulos que se requieren refinar. En particular Rivara ha desarrollado algoritmos basados en la bisección de triángulos por la arista más larga [7, 9]. Resultados recientes sobre estos algoritmos han sido obtenidos por Gutierrez, Gutierrez y Rivara [6]. Dentro de las estrategias que utilizan la bisección de triángulos por la arista más larga, existe una investigación previa efectuada por Rivara y Vénere [13], donde se realiza un análisis geométrico limitado del costo de triangulaciones mediante la bisección de triángulos. En este trabajo no se realiza el estudio empírico de la longitud de propagación del LEPP en el proceso de refinamiento de mallas geométricas, siendo el tema parte del estudio de esta tesis. Por otro lado, Duchaineau et al. discuten el algoritmo ROAM2 [3] que es un método usado en la modelación de terrenos y visualización en tiempo real con mallas de triángulos basado en la noción de un bintree de triángulos rectángulos isósceles (el bintree tiene una variante para triángulos, como lo tiene el quadtree), recursivamente refina los triángulos dividiendo su arista más larga.

1.2.

Definición del problema

El estudio del refinamiento de mallas es un tema teórico de interés. Sin embargo, existen inconvenientes para su análisis:

- Debido a que está supeditado a cada aplicación en particular (los objetos que representan las mallas), es difícil precisar la estructura final de las 2

Real-time Optimally Adapting Meshes.

2

mallas geométricas. La ubicación y distribución de los puntos determinan las características de la malla. - Se desconoce el comportamiento exacto del proceso de refinamiento de mallas geométricas. El resultado varía y depende de los algoritmos de construcción y refinamiento de mallas.

1.2.1.

El problema del refinamiento de triangulaciones

En distintas aplicaciones se necesita resolver el siguiente problema: Dada una triangulación inicial Ti de calidad aceptable3 en particular de triángulos rectángulos isósceles (como los que se muestran en la figura 3.5), una región de refinamiento R de Ti y un parámetro  de longitud de arista más larga requerida; refinar los triángulos que intersectan la región R (por ejemplo el área definida por un cuadrado) construyendo una nueva triangulación Tf que cumpla con las siguientes características:

- La triangulación Tf (refinada) es conforme. - Refinar la región R de modo que todos los triángulos que intersectan R tengan una longitud de la arista más larga menor o igual que . - Mantener triángulos de buena calidad. - Minimizar el costo que involucra la propagación del refinamiento fuera de la región de refinamiento R (operación que se efectúa para la conformidad de la malla). 3

El ángulo más pequeño de la triangulación tiene una cota inferior (α ≥ αcota ).

3

1.3.

Objetivos

1.3.1.

Objetivo general

El objetivo principal de esta tesis es estudiar teórica y empíricamente el proceso de refinamiento según la longitud de la arista más larga sobre los triángulos en mallas geométricas de triángulos rectángulos isósceles y discutir la extensión de estos resultados.

1.3.2.

Objetivos específicos

Estudiar el costo del proceso de refinamiento de mallas de triángulos rectángulos isósceles aplicado a las siguientes condiciones de refinamiento: refinamiento alrededor de un vértice, refinamiento alrededor de una arista, refinamiento de un sector cuadrado y de un sector circular, considerando la longitud de la arista más larga de los triángulos. Determinar la longitud promedio de la propagación del algoritmo de refinamiento bisección LEPP. Estudiar empíricamente el refinamiento de triangulaciones generales obtenidas por vértices aleatorios.

1.4.

Metodología

La investigación se inicia con la revisión bibliográfica, luego se estudia las estrategias de refinamiento de mallas de triángulos rectángulos isósceles con 4

el objetivo de calcular el costo de refinamiento. Por otro lado, se realiza experimentos empíricos sobre mallas Delaunay con el objetivo de calcular la longitud media y máxima de propagación del Lepp (estadística experimental). También se calcula la longitud media de propagación del Lepp utilizando funciones generatrices de probabilidad (estadística teórica). Finalmente esos dos resultados, el experimental y el teórico se contrastan observando las diferencias de las medias y sus desviaciones estándar. Definición de variables. En principio son las siguientes:

El costo del proceso de refinamiento, que se puede medir considerando el número de puntos insertados o el número de triángulos generados. El nivel o la escala de refinamiento, que se puede especificar indicando la máxima longitud  del lado más largo de los triángulos que están en una región de refinamiento.

Para el desarrollo de los experimentos se procede de la siguiente manera: Experimentos. Para los experimentos se genera un conjunto P de puntos aleatorios en el plano, y según sea conveniente se conforman para diferentes tamaños de muestra. Con estos puntos se construyen mallas (triangulaciones) Delaunay. A continuación, estas triangulaciones se refinan considerando los siguientes tipos de refinamiento: alrededor de un vértice, alrededor de una arista, en un sector cuadrado y en un sector circular. Este procedimiento se repite cuarenta veces para cada tamaño de muestra con la finalidad de obtener resultados generales. Para la medición se utiliza una computadora y un programa en lenguaje C/C++. Finalmente se obtiene los resultados y conclusiones.

5

1.5.

Descripción de los Contenidos

En el capítulo Antecedentes se muestra una breve reseña teórica del refinamiento mallas de triángulos. En particular el LEPP (Longest-Edge Propagation Path). En el capítulo Refinamiento de mallas de triángulos rectángulos isósceles se describe el refinamiento de triangulaciones TRI (de Triángulos Rectángulos Isósceles) aplicado a las siguientes condiciones de refinamiento: refinamiento alrededor de un vértice, refinamiento alrededor de una arista, refinamiento de un sector cuadrado y refinamiento de un sector circular. Este capítulo termina explicando el peor caso de refinamiento de las triangulaciones TRI. En el capítulo Estadística experimental de la longitud de propagación del LEPP se realizan experimentos empíricos sobre mallas Delaunay y se obtiene la longitud media y longitud máxima de propagación del LEPP. Las mismas medidas se obtienen en una malla refinada con Lepp-Delaunay. En el capítulo Estadística teórica de la longitud de propagación del LEPP se efectúa el cálculo de la longitud media de propagación LEPP utilizando funciones generatrices de probabilidad. El capítulo culmina comparando los resultados empíricos y teóricos de la longitud media de propagación del Lepp. En el capítulo Conclusiones se resume los resultados obtenidos y se muestra las principales deducciones alcanzadas de los resultados.

6

Capítulo 2 Antecedentes

2.1.

Mallas de triángulos

Las mallas de polígonos (triángulos en particular) sirven para diferentes aplicaciones, por ejemplo, se utilizan ampliamente para representar y aproximar superficies en el espacio, etc. Los modelos de gráficos en computadora por lo general se representan utilizando mallas de triángulos. Una triangulación de un polígono es una partición en un conjunto de triángulos que cubren el polígono, de tal manera que dos triángulos vecinos se intersectan ya sea en un vértice común o en una arista común. Definición 2.1. Una triangulación de un polígono es conforme si para cualquier par de triángulos vecinos se cumple que éstos se intersectan en un vértice común o en una arista común.

Diagrama Voronoi V (P ): Sea P = {p1 , p2 , ..., pn } un conjunto de n puntos 7

distintos en el plano, se define el diagrama Voronoi de P como la subdivisión del plano en n celdas, con la propiedad de que un punto q pertenece a la celda correspondiente al sitio pi , si y sólo si distancia(q, pi ) < distancia(q, pj ) para cada pj ∈ P con j 6= i [2]. Triangulación Delaunay: Sea P = {p1 , p2 , ..., pn } un conjunto de n puntos en

el plano, la Triangulación Delaunay de P se define como el dual del diagrama de Voronoi (tiene un punto para cada celda Voronoi y una arista entre dos puntos si las correspondientes celdas son vecinas). Una propiedad importante es que dado

un conjunto de puntos P , es la triangulación más equilátera descrita en [2, 4] donde también se demuestran las siguientes propiedades: Teorema 2.2. Sea P un conjunto de puntos en el plano.

Tres puntos pi , pj , pk  P son vértices de un mismo triángulo de la triangulación Delaunay de P si y sólo si el círculo formado por pi , pj y pk no contiene en su interior un punto de P . Dos puntos pi , pj  P forman una arista de la triangulación Delaunay de P si y sólo si existe un disco cerrado C que contiene a pi y pj en su límite y no contiene otro punto de P .

El teorema 2.2 implica la siguiente descripción de la triangulación Delaunay. Teorema 2.3. Sea P un conjunto de puntos en el plano, y sea Γ una triangulación de P , entonces Γ es una triangulación Delaunay de P si y sólo si el circuncírculo de cada triángulo de Γ no contiene en su interior un punto de P .

8

2.2.

Refinamiento de triangulaciones mediante la bisección de triángulos

El objetivo principal es refinar triangulaciones de buena calidad, debido a que estos algoritmos mantienen la calidad de la triangulación inicial. Existen algoritmos de refinamiento de triangulaciones basados en la bisección de triángulos [7, 9] por la arista más larga, que garantizan la conservación de la calidad de la triangulación de entrada. Esto debido a las propiedades matemáticas de la bisección de triángulos por la arista más larga [10] y a la estrategia de propagación del área de refinamiento. Como consecuencia, su estudio se ha extendido a tres dimensiones [8, 11, 12]. También existe la partición en cuatro triángulos [10], el que se obtiene uniendo el punto medio del lado más largo con el vértice opuesto y los puntos medios de los dos lados restantes. Observación: Las triangulaciones producidas por la bisección de triángulos en general no son Delaunay.

2.2.1.

Bisección de un triángulo por la arista más larga

Definición 2.4. Sea el triángulo ABC con vértices A, B y C. La bisección del triángulo ABC por la arista más larga se define como sigue. Se forman dos triángulos a partir del triángulo ABC insertando un punto D en la mitad de la arista más larga del triángulo ABC y se traza un segmento desde el punto D al vértice opuesto al lado más largo. Si hay más de un lado de longitud más larga, se selecciona uno de ellos [16].

9

En la figura 2.1 se muestra la bisección del triángulo ABC por su arista más larga. Se inserta el punto D en la mitad de la arista más larga BC y se traza una nueva arista AD, desde el punto D (de la arista BC) al respectivo vértice opuesto. Se forman dos nuevos triángulos ABD y ADC. C

D

B

A

Figura 2.1: Bisección del triángulo ABC por la arista más larga.

2.2.2.

Propiedades de la bisección de un triángulo por la arista más larga

Una propiedad importante de la bisección iterativa de un triángulo en relación a la calidad de triángulos generados es el teorema 2.5 que se explica y demuestra en [7, 16]. Teorema 2.5. La bisección iterativa de un triángulo ABC genera triángulos cuyos ángulos interiores más pequeños son siempre mayores o iguales a α/2, donde α es el ángulo interior más pequeño del triángulo inicial ABC.

También Gutierrez et al. [6] describen las características de los triángulos y en consecuencia el comportamiento del método de bisección.

10

Conformidad de una malla por la bisección de un triángulo: Sea t0 un triángulo de una malla conforme Γ, la bisección de t0 por la arista más larga hace que la malla Γ quede no conforme en el caso de existir un triángulo vecino t1 que comparte con t0 la arista recientemente dividida, debido al punto insertado en la mitad de la arista compartida. De otro modo si la arista más larga del triángulo t0 pertenece al contorno de la malla, entonces Γ permanecerá conforme.

2.2.3.

LEPP (Longest-Edge Propagation Path)

El camino de propagación por la arista más larga de un triángulo t0 (Lepp(t0 )) es una lista ordenada de triángulos t0 , t1 , ..., tn−1 , tn . El LEPP cumple las siguientes propiedades [9, 7]:

ti+1 es el vecino de ti por el lado más largo de ti para i = 0, ..., n − 1. El lado más largo de ti es mayor que el lado más largo de ti−1 . Para cada t0 , Lepp(t0 ) es siempre un conjunto finito1 de triángulos. Para el último triángulo tn de Lepp(t0 ), se cumple que (i) tn tiene su arista más larga en el perímetro y es el de mayor longitud, o bien (ii) tn y tn−1 comparten la misma arista más larga. 1

La propiedad está demostrada.

11

t0 t1 t3 1

t2

(a)

(b)

3

2

2 1

1

(c)

(d) 6

5

4

3

5

4

3

2

2

1

1

(e)

(f)

Figura 2.2: Refinamiento LEPP del triángulo t0 .

2.2.4.

Algoritmo de refinamiento de triangulaciones (Leppbisección)

El algoritmo Lepp-Bisección de refinamiento de triangulaciones por la arista más larga (Lepp-bisección, anteriormente conocido como: Backward LongestEdge Refinement) se ilustra en la figura 2.2, el cual muestra el refinamiento del triángulo t0 sobre una triangulación inicial de la figura 2.2(a). Se observa que Lepp(t0 ) = {t0 , t1 , t2 , t3 }. Las triangulaciones de (b), (c) y (d) muestran los tres

primeros pasos del algoritmo (inserción de los puntos 1, 2 y 3 respectivamente), 12

y (e) es la penúltima triangulación. Finalmente (f) es la malla refinada, donde t0 ha sido dividido. Algoritmo 2.1 LEPP-Bisección(t0 ) Entrada: t0 : Triángulo inicial para el refinamiento. 1: Mientras t0 no esté bisectado Hacer 2: Encontrar Lepp(t0 ) 3: tn ← El último triángulo de Lepp(t0 ) 4: Si tn está en el perímetro Entonces 5: Bisectar tn 6: Sino 7: Bisectar el último par de triángulos tn y tn−1 8: Fin Si 9: Fin Mientras Definición 2.6. Un triángulo t es casi equilátero si se comporta como un triángulo equilátero en su bisección: En la primera bisección por la arista más larga se introduce una mediana no paralela a los lados de t, y las posteriores medianas son paralelas a algún lado de t.

Observación: Las triangulaciones compuestas por triángulos rectángulos isósceles son casi equiláteras, su ángulo mínimo esta acotado por π4 .

2.3.

Refinamiento de mallas Delaunay

En esta sección se revisan otros algoritmos de refinamiento de mallas, específicamente los que trabajan en mallas Delaunay. El objetivo principal de los algoritmos de refinamiento de mallas Delaunay es insertar nuevos puntos en lugares estratégicos con el objetivo de eliminar elementos de baja calidad, de tal manera que ningún vértice caiga dentro del 13

circuncírculo de los triángulos, manteniendo las propiedades Delaunay y por lo tanto mejorando la calidad de la malla resultante. A continuación se revisan los algoritmos más destacados de refinamiento de mallas Delaunay. Entre los primeros algoritmos de refinamiento de mallas Delaunay que se introdujeron está el de Ruppert [17] tal vez el primero de los que son teóricamente garantizados, Ruppert prueba que su algoritmo produce mallas con ángulos no más pequeños que 20,7◦ . Es la extensión de un anterior algoritmo de Chew (cuyo primer algoritmo de refinamiento no permite triángulos de diferentes tamaños). La estrategia del algoritmo es hacer mejoras locales con el objetivo de eliminar triángulos flacos (triángulos que tienen algún ángulo menor a una cota α). Cada mejora implica agregar un nuevo vértice a la triangulación y en consecuencia volver a triangular. Los lados (arcos) del grafo de líneas rectas en el plano (planar straightline graph PSLG en ingles) se denominan como segmentos para distinguir de los lados de la triangulación Delaunay. Las dos operaciones básicas en el algoritmo son dividir un segmento añadiendo un vértice en su mitad, y dividir un triángulo añadiendo un vértice en su circuncentro2 . Para un segmento S el círculo con S como diámetro es referido como su círculo diametral, y se dice que un vértice invade un segmento S si cae en el círculo diametral de S. En esencia el algoritmo divide triángulos flacos añadiendo un vértice en su circuncentro que puede caer no necesariamente en el triángulo vecino adyacente, a menos que el circuncírculo del triángulo invada algún segmento, en tal caso se divide el segmento (o los segmentos invadidos) en lugar del triángulo. 2

Es el punto en que se cortan las tres mediatrices de los lados de un triángulo y es el centro de la circunferencia circunscrita.

14

La estrategia elaborada por Shewchuk [19] combina el algoritmo de Ruppert [17] y el algoritmo de Chew [1] reemplazando el círculos diametrales por lentes diametrales, de este modo un segmento se considera invadido siempre que un vértice cae dentro del lente diametral (este y otros arreglos además). El lente diametral de un subsegmento S es la intersección de dos discos con la capacidad de almacenar un triángulo isósceles cuyos ángulos en la base S son 30◦ . Otra extensión de Shewchuk para el algoritmo de Ruppert se puede encontrar en [20]. Existe un refinador de mallas denominado Triangle [18] desarrollado por Shewchuk que está disponible en la dirección Web del autor en http://www.cs. cmu.edu/~quake/triangle.html y en Netlib3 . Construido en el lenguaje C para generación de mallas en dos dimensiones sirve para la construcción de triangulaciones Delaunay, triangulaciones Delaunay restringido, diagramas de Voronoi y mallas de triángulos de alta calidad (en la versión 1.6). El autor en [18] discute los tópicos de implementación como la estructura de datos, los pasos para crear y refinar una malla y el uso de aritmética exacta para mejorar la robustez del programa, finalmente recomienda para el análisis de elementos finitos. También existe el algoritmo Lepp-Delaunay [12, 14, 15] utiliza la propagación por la arista más larga de triángulos de mala calidad. Se inserta un vértice en la arista terminal del LEPP como lo hace el algoritmo Lepp-Bisección. Para cumplir las propiedades Delaunay, en la inserción de los vértices se aplica el procedimiento de intercambio de aristas (del algoritmo Delaunay) sobre cada uno de los triángulos nuevos y sobre algunos de sus vecinos hasta obtener una nueva malla Delaunay.

3

Netlib es una colección que está a libre disposición contiene Software, documentos y bases de datos de interés para la comunidad de computación científica, numérica y otros. Su dirección Web es http://www.netlib.org.

15

Capítulo 3 Refinamiento de mallas de triángulos rectángulos isósceles

3.1.

El problema de refinamiento de triángulos rectángulos isósceles

En este capítulo se estudia las triangulaciones compuestas de triángulos rectángulos isósceles (TRI en este capítulo). Se explica que las mallas conformadas por triángulos rectángulos son Delaunay. También se expone el motivo por el que en este capítulo se estudian exclusivamente las mallas compuestas de triángulos rectángulos isósceles (TRI). Triángulo rectángulo isósceles: Un triángulo rectángulo isósceles ABC tiene un ángulo recto C (π/2 radianes) y dos agudos iguales (π/4 cada uno). Los lados iguales son los catetos y el diferente es la hipotenusa. Si se divide la arista más larga AB de un triángulo rectángulo isósceles ABC por el punto medio M 16

de AB y el vértice opuesto C, se obtiene dos nuevos triángulos rectángulos isósceles iguales ACB y BCM, esto se ilustra en la figura 3.1. Luego, la bisección de un triángulo rectángulo isósceles genera necesariamente dos nuevos triángulos rectángulos isósceles idénticos. A• π/4 •M π/2 C•

•B

Figura 3.1: Bisección de un triángulo rectángulo isósceles. Triángulo rectángulo escaleno: Un triángulo rectángulo escaleno ABC tiene un ángulo recto C (π/2 radianes) y todos sus lados y ángulos son diferentes. La bisección de un triángulo rectángulo escaleno por el punto medio M del lado más largo AB y el vértice opuesto C, no genera nuevos triángulos rectángulos, por lo que no son considerados en esta sección. A•

π/2 C•

•M •B

Figura 3.2: Bisección de un triángulo rectángulo escaleno. Teorema 3.1. Todas las mallas de triángulos rectángulos son Delaunay.

Demostración. El circuncírculo de un triángulo rectángulo ABC no puede contener en su interior al tercer vértice no común D de un triángulo rectángulo vecino BCD que comparten el lado BC o cualquiera de los otros dos lados sin 17

perder generalidad. Por contradicción, si el vértice no común D estuviera dentro del circuncírculo, entonces el ángulo que representa (respecto al lado BC) sería mayor que π/2 y por lo tanto no sería un triángulo rectángulo. De esta manera, en secuencia todos los triángulos rectángulos vecinos cumplen la prueba del circuncírculo de Delaunay. Luego todas las mallas de triángulos rectángulos son Delaunay.

Por ejemplo en la figura 3.3 el triángulo rectángulo ABC tiene dos vecinos el triángulo rectángulo BCD y ABE. El circuncírculo del triángulo rectángulo ABC no contiene en su interior a los vértices D y E de sus vecinos. El vértice D cae en el límite del circuncírculo y el vértice E está en el exterior. •D C • A •

•

• B

• E

Figura 3.3: Triangulación Delaunay compuesta por triángulos rectángulos (isósceles o no isósceles). Corolario 3.2. Todas las mallas de triángulos rectángulos isósceles son Delaunay.

Observación: La inserción de un vértice M en el circuncentro de un triángulo rectángulo isósceles T es la misma inserción que se realiza al insertar un vértice en el lado más largo de T (producto de la bisección). Si a un triángulo rectángulo isósceles T , por ejemplo, el de la figura 3.1 se le agrega el circuncírculo entonces el circuncentro cae justamente en M, que es el punto medio de la hipotenusa, como se vuelve a mostrar en la figura 3.4. 18

A• π/4 •M π/2 C•

•B

Figura 3.4: Inserción de un vértice en el circuncentro de un triángulo rectángulo isósceles.

3.2.

Triangulación uniforme TRI

Definición 3.3. Triangulación uniforme TRI: Es una triangulación compuesta de triángulos rectángulos isósceles, donde todos los triángulos son del mismo tamaño. En la figura 3.5 se pueden observar algunos ejemplos.

(a)

(b)

(c)

Figura 3.5: Malla de triángulos rectángulos isósceles. Propiedad 3.4. En una triangulación uniforme TRI, los triángulos son del mismo tamaño y cada triángulo ti puede tener hasta tres vecinos. Los catetos de ti pueden tener vecinos que comparten también sus catetos, debido a que la longitud del cateto es distinta al de la hipotenusa. Del mismo modo, a la hipotenusa de ti le corresponde un vecino que comparte también su hipotenusa. 19

Teorema 3.5. En una malla uniforme TRI la longitud de propagación por la arista más larga de un triángulo es a lo más dos. Dos si el triángulo tiene un vecino por la hipotenusa o uno si el triángulo tiene su hipotenusa en el borde de la malla.

Demostración. De acuerdo a la propiedad (3.4) en una malla uniforme TRI, si a la hipotenusa de un triángulo tiene un vecino entonces ambos comparten sus aristas más largas y en consecuencia la longitud de propagación LEPP es dos. Y si la hipotenusa cae en el borde de la malla entonces la longitud de propagación LEPP es uno. Corolario 3.6. En una malla uniforme TRI la bisección por la arista más larga de cualquier triángulo no tiene el peor caso de propagación.

Observación: Una triangulación no uniforme está compuesta de triángulos rectángulos isósceles de diferentes tamaños. Una triangulación general TRI puede ser uniforme o no uniforme. Definición 3.7. El problema de refinamiento de mallas compuestas de triángulos rectángulos isósceles es como sigue: Dada una triangulación uniforme inicial Mi de triángulos rectángulos isósceles, una región de refinamiento R de Mi y un parámetro de longitud de arista ; obtener una triangulación refinada1 y conforme Mf de triángulos rectángulos isósceles, tal que la longitud de la arista más larga de cada triángulo de Mf que intersecta R sea menor o igual que .

La región R de refinamiento que se consideran son las siguientes: alrededor de un vértice, alrededor de una arista, dentro del área definida por un cuadrado 1

Insertando puntos y generando nuevos triángulos rectángulos isósceles por efecto de la bisección iterativa de los mismos.

20

y dentro del área definida por un círculo. El área de la región R puede ser incluso igual a cero (aunque se puede esperar que sea distinta de cero), en el caso del refinamiento alrededor de un vértice (punto) el área del sector R es cero, lo mismo sucede si el refinamiento es alrededor de una arista.

3.3. 3.3.1.

Refinamiento alrededor de un vértice Refinamiento alrededor de un vértice para una triangulación TRI de cuatro triángulos (figura 3.6(a))

Se considera el caso de refinamiento estable de una triangulación, es decir, cuando el refinamiento es local y presenta un comportamiento que sigue un patrón. Motivo por el cual se pueden obtener resultados exactos. Por ejemplo la figura 3.6(a) se refina utilizando seis iteraciones, una iteración consiste en la división de todos los triángulos que comparten el vértice común P . El resultado se muestra en la figura 3.6(b) con la inserción de 24 vértices y 44 triángulos en seis iteraciones, y si se considera los 5 vértices y 4 triángulos iniciales, hacen un total de 29 vértices y 48 triángulos.

21

L •

• •

•

•

• • • • • • • • • • • • • • • • • • • •

•

• (b)

•

• P •

•

(a)

•

• •

Figura 3.6: Refinamiento alrededor de un vértice P : (a) Malla inicial y (b) Malla refinada en seis iteraciones. Supuesto 3.8. Se consideran sólo triangulaciones conformadas por triángulos rectángulos isósceles TRI. Definición 3.9. Triangulación inicial Tv para refinar alrededor de un vértice: La triangulación inicial Tv para refinar alrededor de un vértice es la mostrada en la figura 3.6(a). El refinamiento se realiza alrededor de un vértice interior P donde se unen los vértices y ángulos internos adyacentes iguales de (cuatro) triángulos rectángulos isósceles con longitudes iniciales de hipotenusas L. Problema 3.10. Refinamiento alrededor de un vértice: Dada una triangulación inicial Tv , un vértice P y un parámetro de longitud de arista , se requiere refinar el sector definido por un vértice P de Tv , tal que la longitud de la arista más larga de cada triángulo de vértice común P sea menor o igual que . Teorema 3.11. Refinamiento alrededor de un vértice: Para el problema 3.10 sobre la triangulación Tv de la definición 3.9. El número de vértices insertados y el número de triángulos generados alrededor de un vértice común P utilizando el algoritmo Bisección-Lepp es igual a 8 log2 22

  L 

y 16 log2

  L 

− 4, respectivamente.

Demostración. El objetivo es calcular el número de vértices insertados y triángulos generados, de acuerdo a la longitud de arista (más larga) deseada  que indica hasta que longitud debe reducirse la arista (más larga) inicial L de los triángulos que comparten el vértice común P . Aparte de la triangulación Tv y el vértice P , los parámetros de entrada serán L y . • P •

•

• •

•

•

•

•

•

• •

•

•

(a) • • •

• • •

• •

•

(b)

•

• • •

•

• •

(c)

•

•

•

•

•

•

•

•

•

•

•

•

•

•

(d)

Figura 3.7: Iteraciones del refinamiento alrededor del vértice P : (a) Triangulación inicial, (b) Primera, (c) Segunda y (d) Tercera iteración. El comportamiento se muestra en la figura 3.7, donde se observa que desde la segunda iteración expresa un comportamiento estable, es decir, el número de vértices y triángulos agregados es constante en cada paso iterativo (en particular se agregan cuatro vértices y ocho triángulos). Se cumple también que el número de aristas que están conectadas al vértice P es ocho. En la tabla 3.1 se registran los pasos. Número de vértices insertados: La cantidad de triángulos rectángulos isósceles que pueden rodear un vértice compartido P es cuatro y ocho (con cuatro ángulos rectos y ocho ángulos de π/4 respectivamente), en estos dos casos el número de vértices insertados en cada iteración es cuatro vértices, el com23

Itera- Vértices Total vér- Triángulos Total ción inserta- tices p(n) insertatriángulos dos dos t(n) 1 2 3 4 5 6 7 ... n

4 4 4 4 4 4 4 ... 4

4 8 12 16 20 24 28 ... p(n−1)+4

4 8 8 8 8 8 8 ... 8

4 12 20 28 36 44 52 ... t(n − 1) + 8

Arista más larga h(n) √ 2L/2 L/2 √ 2L/4 L/4 √ 2L/8 L/8 √ 2L/16 ... h(n−1) √ 2

Tabla 3.1: Vértices y triángulos insertados en el refinamiento alrededor de un vértice. portamiento incremental se describe en la tabla 3.1. Luego, el número total de vértices insertados p(n) en función del número de iteraciones n, queda definido por la ecuación p(n) = p(n − 1) + 4 con p(1) = 4, el desarrollo de la ecuación recursiva es:

p(n) = 4n

(3.1)

Número de triángulos insertados: El mismo procedimiento se efectúa considerando que en cada iteración se agregan ocho triángulos. En consecuencia, el número de triángulos generados t(n) en función del número de iteraciones n, está definido por la ecuación t(n) = t(n − 1) + 8 con t(1) = 4, es decir:

t(n) = 8n − 4

24

(3.2)

Bisección de la arista más larga: La arista más larga de cada triángulo que comparte el vértice común P , se reduce multiplicándose por

√

2 2

en cada ite-

ración, este factor se obtiene con la aplicación del teorema de Pitágoras en las bisecciones sucesivas de un triángulo rectángulo isósceles. Luego la longitud de la arista más larga h(n) en función del número de iteraciones n, queda definida √ por la ecuación h(n) = h(n − 1)/ 2 con h(0) = L, cuya fórmula no recursiva es

(sexta columna de la tabla 3.1):

h(n) =

L n 22

(3.3)

Debido a que se requiere expresar las ecuaciones en función de la arista deseada , se despeja n de la ecuación 3.3 reemplazando h(n) por , obteniéndose:

n = 2 log2



L 



(3.4)

Finalmente se calcula el número de vértices y triángulos agregados considerando que la longitud de la arista más larga de cada triángulo de vértice común P sea menor o igual que un parámetro de entrada . Reemplazando la ecuación 3.4 en la ecuación 3.1 y 3.2 se obtiene:

p(L, ) = 8 log2

t(L, ) = 16 log2

25





L 



(3.5)

L −4 

(3.6)



En este caso, el trabajo de bisección se realiza sólo en los triángulos que comparten el vértice común P , no hay propagación en el resto de la malla.

3.3.2.

Algoritmo para el refinamiento alrededor de un vértice

El trabajo consiste en dividir los triángulos que están alrededor de un único vértice de referencia P , esto hace que el algoritmo (3.1) sea simple. El algoritmo recibe como parámetro de entrada P , L y .

P : Vértice de referencia alrededor del cual se refina. L : Longitud de la arista inicial de los triángulos con vértice común P .  : Longitud de la arista requerida para los triángulos con vértice común P .

Las aristas de los triángulos rectángulos isósceles de vértice común P tienen una misma longitud por lo que para representarlas se puede utilizar una varia√ ble, en el algoritmo es longitud_arista, y se divide por 2 en cada paso iterativo de bisección. Las iteraciones terminan cuando la longitud de arista (longitud_arista) deja de ser mayor que , es decir, cuando los triángulos refinados han alcanzado la dimensión requerida.

26

Algoritmo 3.1 Refinamiento_alrededor_de_un_vértice(P ,L,) Entrada: P : Vértice de referencia alrededor del cual se refina. Entrada: L : Longitud de la arista inicial de los triángulos con vértice común P. Entrada:  : Longitud de la arista requerida para los triángulos con vértice común P . 1: longitud_arista ← L 2: Mientras longitud_arista >  Hacer 3: Para cada triángulo t con vértice común P Hacer 4: Lepp_Bisección(t) 5: Fin Para √ 6: longitud_arista ← longitud_arista 2 7: Fin Mientras

En el refinamiento alrededor de un vértice, existen mallas en los que la bisección de un triángulo puede involucrar la bisección de otros los triángulos de la malla. El algoritmo recursivo Lepp-Bisección efectúa la bisección de los triángulos de vértice común P cuidando la conformidad de la malla.

3.3.3.

Refinamiento alrededor de un vértice para una triangulación uniforme TRI

Teorema 3.12. En una triangulación uniforme TRI, el número de vértices insertados y el número de triángulos rectángulos isósceles generados alrededor de un vértice común P utilizando el algoritmo Bisección-Lepp es una función logarítmica de L .

Demostración. La demostración sigue al teorema 3.11, donde el número de vértices insertados y el número de triángulos generados alrededor de un vértice común P utilizando el algoritmo Bisección-Lepp es una función logarítmica de 27

L , 

esto viene a ser un caso particular de refinamiento estable, es decir, cuando el

refinamiento es local y sin el peor caso de propagación en la malla. Para generalizar este resultado se requiere demostrar que en las triangulaciones uniformes TRI no existe el peor caso de propagación. El corolario 3.6 sustenta que en una malla uniforme TRI la bisección por la arista más larga de un triángulo no tiene el peor caso de propagación.

3.4. 3.4.1.

Refinamiento alrededor de una arista Refinamiento alrededor de una arista para la triangulación TRI de la figura 3.8.(b)

Se considera el caso de refinamiento estable de una triangulación, donde el refinamiento es local y presenta un comportamiento que sigue un patrón. Motivo por el cual se pueden obtener resultados exactos. Supuesto 3.13. Se consideran sólo triangulaciones conformadas por triángulos rectángulos isósceles TRI. Definición 3.14. Triangulación inicial Ta para refinar alrededor de una arista: La triangulación inicial Ta para refinar alrededor de una arista es la mostrada en la figura 3.8.(b). El refinamiento se realiza sobre los triángulos que están alrededor de una arista AB de longitud L donde se unen los lados de (dos) triángulos rectángulos isósceles con longitudes iniciales de hipotenusas L (simétricamente distribuidos y sin solapamiento). Problema 3.15. Refinamiento alrededor de una arista: Dada una triangulación inicial Ta , un arista inicial AB y un parámetro de longitud de arista , se 28

requiere refinar el sector definido por una arista AB de Ta , tal que la longitud de la arista más larga de cada triángulo cuya arista es segmento de AB sea menor o igual que . Teorema 3.16. Refinamiento alrededor de una arista: Para el problema 3.15 sobre la triangulación Ta de la definición 3.14. El número de vértices insertados y el número de triángulos generados alrededor de una arista común AB utilizando el algoritmo Bisección-Lepp es igual a:

  

  L 

+ 8 log2

  L 

−7 si n es par   p(L, ) =  √   L L  4 2 + 8 log2  − 11 si n es impar  7

y

  

 

 

si n es par 14 L + 16 log2 L − 14     t(L, ) = √   8 2 L + 16 log L − 22 si n es impar 2   respectivamente.

Demostración. En la figura 3.8 contiene dos mallas iniciales (a) y (b), en donde (b) está adecuada para obtener las fórmulas. El segmento AB que está definido por los vértices A y B, inicialmente es la arista que comparten dos triángulos, posteriormente AB contiene subsegmentos que son aristas de los triángulos bisectados. Los triángulos cuyas aristas son segmentos de AB, no necesariamente pertenecen a AB con sus hipotenusas (la arista más larga) sino también con cualquiera de sus dos catetos (figura 3.9). Una iteración consiste en la división de todos los triángulos cuyas aristas son segmentos de AB, de esta manera, la primera iteración comienza con los dos triángulos que comparten la

29

arista común AB, se bisecta el segmento AB en dos subsegmentos (conformando nuevos triángulos), éstos a su vez son bisectados en otros subsegmentos, así sucesivamente. L

A

B

(a) L

A

B

(b) Figura 3.8: Refinamiento alrededor de una arista: (a) y (b) son triangulaciones iniciales para el refinamiento alrededor de la arista definida por los vértices A y B.

El objetivo es calcular el número de vértices insertados y triángulos generados, de acuerdo a la longitud de arista deseada  que indica hasta qué longitud debe reducirse las aristas más largas de los triángulos cuyas aristas son segmentos de AB. La longitud AB es L.

30

A

B

(a)

(b)

(c)

(d)

(e)

(f)

Figura 3.9: Iteraciones del refinamiento alrededor de la arista AB: (a) Triangulación inicial, (b) Primera, (c) Segunda, (d) Tercera, (e) Cuarta y (f) Quinta iteración.

El comportamiento se muestra en la figura 3.9, donde se observa que en las iteraciones impares (primera, tercera, etc.) la inclusión de vértices y triángulos es en progresión geométrica de potencias de dos (debido a la bisección de los triángulos). Es similar en las iteraciones pares, que además tiene una constante. En la tabla 3.2 se registran los pasos. Número de vértices insertados: El número de vértices insertados en cada iteración es la mitad del número de triángulos agregados, esto debido a que por cada dos triángulos agregados se inserta un nuevo vértice, el vértice queda rodeado por cuatro triángulos nuevos en donde anteriormente eran sólo dos 31

Iteración

1 2 3 4 5 6 7 8 ... n

Vértices insertados

Total vértices p(n) 1−1 2 2 = 1 1 2 2 −1 2(2 2 − 1) + 2(2 2 ) + 10 = 14 15 3−1 2 2 = 2 17 4 4 2(2 2 −1 − 1) + 2(2 2 ) + 10 = 20 37 5−1 2 2 = 4 41 6 6 2(2 2 −1 − 1) + 2(2 2 ) + 10 = 32 73 7−1 2 2 = 8 81 8 8 2(2 2 −1 − 1) + 2(2 2 ) + 10 = 56 137 ... ... (*) (*) (*) Depende si n es par o impar.

Tabla 3.2: Vértices insertados en el refinamiento alrededor de una arista. (ver los cálculos del número de triángulos insertados). La ecuación 3.7 es exactamente la mitad de la ecuación 3.9. El comportamiento incremental se describe en la tabla 3.2. Luego, el número total de vértices insertados p(n) en función del número de iteraciones n, queda definido por la siguiente ecuación con p(1) = 1:

p(n) =

    



n



p(n − 1) + 3 2 2 + 8 si n es par n

1

p(n − 1) + 2 2 − 2

si n es impar

(3.7)

El resultado para el número de vértices insertados es:

p(n) =

    



n



7 2 2 + 4n − 7 

4 2

 n+1 2

si n es par

+ 4n − 11 si n es impar

(3.8)

Número de triángulos insertados: La inserción de triángulos se clasifi32

ca en dos casos: las iteraciones pares y las impares, esto debido a su comportamiento incremental. Cuando el número de la iteraciones es par el número de n

triángulos cuyas aristas son segmentos de AB es de 2 2 a cada lado (donde n es el número de iteración) debido a que únicamente en cada dos iteraciones se bisectan las aristas que son segmentos de AB (figura 3.9). Se tiene la misma n

cantidad de triángulos en ambos lados, sumando un total de 2 2 +1 triángulos. La propagación necesaria para la conformidad de la malla genera nuevos triángulos, y por cada triángulos cuya arista es segmento de AB, la propagación es de seis nuevos triángulos menos los tres iniciales bisectados, es decir, tres triángu

n



los adicionales. Luego se agregan 3 2 2 +1 triángulos más 16 triángulos provenientes de la propagación adicional de los cuatro triángulos que están en los extremos, quienes se propagan añadiendo cuatro triángulos cada uno. En el caso que la iteración sea impar, el número de triángulos cuyas aristas son segmentos n

1

de AB es de 2 2 + 2 . La propagación genera nuevos triángulos, en este caso por cada triángulo cuya arista es segmento de AB, la propagación es de dos triánn

1

gulos nuevos menos uno inicial bisectado, es decir, uno. Luego se agregan 2 2 + 2

triángulos. Finalmente, el número de triángulos generados t(n) en función del número de iteraciones n, está definido por la ecuación:

t(n) =

    





n

t(n − 1) + 3 2 2 +1 + 16 si n es par n

1

t(n − 1) + 2 2 + 2

si n es impar

(3.9)

La sumatoria para encontrar la ecuación resultado para el número de triángulos agregados es:

t(n) =

 P n2   P  

k=1

3 2i+1 + 16 +

n+1 2

n+1 2

i k=1 2 +

P




k=2





i

P n2

k=1 2

3 2 + 16

33




i

si n es par si n es impar

(3.10)

Itera- Triángulos insertados ción

Total Arista más triángulos larga h(n) t(n) √ 1+1 2 =2 2 2 2L/2 2+2 3(2 2 ) + 16 = 28 30 L/2 √ 3+1 2 2 = 4 34 2L/4 4+2 3(2 2 ) + 16 = 40 74 L/4 √ 5+1 2 2 = 8 82 2L/8 6+2 3(2 2 ) + 16 = 64 146 L/8 √ 7+1 2 2 = 16 162 2L/16 8+2 2 3(2 ) + 16 = 112 274 L/8 ... ... ... √ (*) (*) h(n) = h(n−1) 2 (*) Depende si n es par o impar.

1 2 3 4 5 6 7 8 ... n

Tabla 3.3: Triángulos insertados en el refinamiento alrededor de una arista. El resultado para el número de triángulos agregados es:

  

t(n) =  



n



14 2 2 + 8n − 14 

8 2

n+1 2



si n es par

+ 8n − 22 si n es impar

(3.11)

Bisección de la arista más larga: El resultado es el mismo del refinamiento alrededor de un vértice, la arista más larga de cada triángulo, se reduce multiplicándose por

√

2 2

en cada iteración, este factor se obtiene con la aplicación del

teorema de Pitágoras en las bisecciones sucesivas de un triángulo rectángulo isósceles. Luego la longitud de la arista más larga h(n) en función del número √ de iteraciones n, queda definida por la ecuación h(n) = h(n − 1)/ 2 con h(0) = L,

cuya fórmula no recursiva es (cuarta columna de la tabla 3.3):

h(n) = 34

L n 22

(3.12)

Debido a que se requiere expresar las ecuaciones en función de la arista deseada , se despeja n de la ecuación 3.12 reemplazando h(n) por , obteniéndose:

n = 2 log2



L 



(3.13)

Finalmente se calcula el número de vértices y triángulos agregados considerando que la longitud de la arista más larga de cada triángulo cuya arista es segmento de E sea menor o igual que un parámetro de entrada . Reemplazando la ecuación 3.13 en la ecuación 3.8 y 3.11 se obtiene:

p(L, ) =

  

7

  L 

√   4 2

  

+ 8 log2

  L 

 

  L 

+ 8 log2

−7

  L 

si n es par

− 11 si n es impar

 

14 L + 16 log2 L − 14 si n es par     t(L, ) = √   8 2 L + 16 log L − 22 si n es impar 2  

3.4.2.

(3.14)

(3.15)

Algoritmo para el refinamiento alrededor de una arista

El trabajo consiste en dividir los triángulos que están alrededor de una arista inicial AB, el algoritmo (3.2) expone los detalles. El algoritmo recibe como parámetro de entrada AB, L y .

E : Arista (segmento) de referencia alrededor del cual se refina.

35

L : Longitud de la arista inicial de los (dos) triángulos con arista común AB.  : Longitud de la arista requerida para los triángulos cuyas aristas son segmentos de AB.

Las hipotenusas de los triángulos rectángulos isósceles cuyas aristas son segmentos de AB tienen una misma longitud por lo que para representarlas se √ puede utilizar una variable, en el algoritmo es longitud_arista, y se divide por 2 en cada paso iterativo de bisección. Las iteraciones terminan cuando la longitud de arista (longitud_arista) deja de ser mayor que , es decir, cuando los triángulos refinados han alcanzado la dimensión requerida. Algoritmo 3.2 Refinamiento_alrededor_de_una_arista(AB,L,) Entrada: AB : Arista (segmento) de referencia alrededor del cual se refina. Entrada: L : Longitud de la arista inicial de los triángulos con arista común AB. Entrada:  : Longitud de la arista requerida para los triángulos cuyas aristas son segmentos de AB. 1: longitud_arista ← L 2: Mientras longitud_arista >  Hacer 3: Para cada triángulo t con arista ∈ AB Hacer 4: Lepp_Bisección(t) 5: Fin Para √ 6: longitud_arista ← longitud_arista 2 7: Fin Mientras

En la línea cuatro del algoritmo 3.2 se utiliza el algoritmo recursivo 2.1 para la bisección del triángulo t y sus vecinos, es decir Lepp(t), esto para la conformidad de la malla.

36

3.4.3.

Refinamiento alrededor de una arista para una triangulación uniforme TRI

Teorema 3.17. En una triangulación uniforme TRI, el número de vértices insertados y el número de triángulos rectángulos isósceles generados alrededor de una arista común AB de longitud L utilizando el algoritmo Bisección-Lepp es una función lineal de L .

Demostración. La demostración sigue al teorema 3.16, donde el número de vértices insertados y el número de triángulos generados alrededor de una arista común AB de longitud L utilizando el algoritmo Bisección-Lepp es una función lineal de

L , 

esto viene a ser un caso particular de refinamiento estable, es de-

cir, cuando el refinamiento es local y sin el peor caso de propagación en la malla. Para generalizar este resultado se requiere demostrar que en las triangulaciones uniformes TRI no existe el peor caso de propagación. El corolario 3.6 sustenta que en una malla uniforme TRI la bisección por la arista más larga de un triángulo no tiene el peor caso de propagación.

3.5. 3.5.1.

Refinamiento de un sector cuadrado Refinamiento de un sector cuadrado para una triangulación TRI de la figura 3.10

Se considera el caso de refinamiento estable de una triangulación, donde el refinamiento es local y presenta un comportamiento que sigue un patrón. Motivo por el cual se pueden obtener resultados exactos. 37

Supuesto 3.18. Se consideran sólo triangulaciones conformadas por triángulos rectángulos isósceles TRI. Definición 3.19. Triangulación inicial Ts para refinar un sector cuadrado: La triangulación inicial Ts para refinar un sector cuadrado es la mostrada en la figura 3.10. El refinamiento se realiza en un sector cuadrado ABCD con lado de longitud L y centro P , donde se unen los vértices y ángulos internos adyacentes iguales de (cuatro) triángulos rectángulos isósceles con longitudes iniciales de hipotenusas L. Problema 3.20. Refinamiento de un sector cuadrado: Dada una triangulación inicial Ts , un cuadrado ABCD y un parámetro de longitud de arista , se requiere refinar el sector definido por un cuadrado ABCD dentro de Ts , tal que la longitud de la arista más larga de cada triángulo contenido en ABCD sea menor o igual que . Teorema 3.21. Refinamiento de un sector cuadrado: Para el problema 3.20 sobre la triangulación Ts de la definición 3.19. El número de vértices insertados y el número de triángulos rectángulos isósceles generados dentro y fuera de un sector cuadrado utilizando el algoritmo Bisección-Lepp es igual a:

p(L, ) =

    

 2

L   2 4 L

2

  √   + 8 2 L + 8 log2 L − 15 si

+1

si

L  L 

es par es impar

y

t(L, ) =

    

 2

L   2 4 L

4

  √   + 16 2 L + 16 log2 L − 36 si

si

respectivamente. 38

L  L 

es par es impar

D

C

L

B

A

Figura 3.10: Refinamiento de un sector cuadrado ABCD. Demostración. El objetivo es calcular el número de vértices insertados y triángulos generados, de acuerdo a la longitud de arista deseada  que indica hasta qué longitud debe reducirse la arista de los triángulos contenidos en un cuadrado ABCD de la figura 3.10. La medida puede expresarse con la proporción L/. La solución está compuesta por dos partes: (A) Lo que se genera dentro del área del cuadrado y (B) Lo que se genera fuera de la región del cuadrado, esto para la conformidad de la malla. A. Refinamiento dentro del área de un sector cuadrado El comportamiento del refinamiento por iteraciones se muestra en la figura 3.11, donde se grafica exclusivamente el sector ABCD de la figura 3.10. El resto del gráfico se omite debido a que en la primera parte se estudia parcialmente el refinamiento en el interior de un cuadrado. Se observa que a diferencia del refinamiento alrededor de un vértice, el número de vértices y triángulos agregados no es constante en cada paso iterativo de división de los triángulos. En este caso es exponencial como se observa en la tabla 3.4 donde se distingue mejor el número de vértices y triángulos agregados. 39

•

• •

•

•

•

•

•

• •

•

•

• • •

• •

•

• (b) •

•

•

•

•

•

• •

•

•

•

•

•

•

•

•

•

• •

•

• (d)

•

•

• •

(a) • •

•

• •

• • (c)

•

Figura 3.11: Refinamiento dentro del área de un sector cuadrado Ω. De acuerdo al comportamiento incremental descrito en la tabla 3.4, el número de vértices insertados dentro del área definida por el cuadrado está definido por la siguiente ecuación, que indica el número de vértices insertados p(n) en función del número de iteraciones n:

p(n) =

    

2n + 2

n+2 2

+ 1 si n es par

2n + 2

n+1 2

+ 1 si n es impar

(3.16)

De igual manera se efectúa para el número de triángulos generados, definido por la ecuación t(n) = 2 ∗ t(n − 1) con t(1) = 4, que indica el número de triángulos generados t(n) en función del número de iteraciones n:

t(n) = 2n+1

40

(3.17)

Itera- Vértices Total vér- Triángulos Total ción insertices p(n) insertatriángulos tados dos en el t(n) en el interior interior 1 1 5 4 4 2 4 9 4 8 3 4 13 8 16 4 12 25 16 32 5 16 41 32 64 6 40 81 64 128 7 64 145 128 256 ... ... ... ... ... n (*) − 2n+1 (*) Depende si n es par o impar.

Arista más larga h(n) L √

2L/2 L/2 √ 2L/4 L/4 √ 2L/8 L/8 ... h(n−1) √ 2

Tabla 3.4: Refinamiento por iteraciones dentro del área de un sector cuadrado. La arista más larga de los triángulos contenidos en el cuadrado ABCD en función del número de iteraciones n (sexta columna de la tabla 3.4) está definida por:

L

h(n) =

2

n−1 2

(3.18)

Luego se despeja n de la ecuación 3.18, obteniéndose:

n = 2 log2



L +1  

(3.19)

Finalmente se calcula el número de vértices y triángulos agregados considerando que la longitud de la arista más larga de cada triángulo dentro de ABCD sea menor o igual que un parámetro de entrada . Reemplazando la 41

ecuación 3.19 en las ecuaciones 3.16 y 3.17 se obtiene:

p(L, ) =

 √ 2  2L  + 1   2   2L + 1 

t(L, ) =



si si

2L 

L  L 

es par es impar

2

(3.20)

(3.21)

Considerando los resultados de estas dos últimas fórmulas. El número de vértices insertados y el número de triángulos rectángulos isósceles generados exclusivamente dentro de un sector cuadrado es una función cuadrática. Este resultado es la solución parcial del problema definido inicialmente en la sección 3.5.1. B. Refinamiento en el exterior de un sector cuadrado El comportamiento se muestra en la figura 3.12, donde se grafica los vértices agregados sólo en el exterior del cuadrado ABCD, no se consideran los vértices insertados en el interior debido a que en esta parte se estudia el comportamiento en el exterior de un cuadrado. Los vértices de color negro son los que han sido insertados en las iteraciones anteriores a la reciente iteración, los nuevos vértices insertados son de color azul. El número de vértices y triángulos agregados es exponencial como se observa en la tabla 3.5. De acuerdo al comportamiento incremental descrito en la tabla 3.5, el número de vértices insertados en el exterior del área definida por el cuadrado está definido por la siguiente ecuación, que indica el número de vértices insertados p(n) en función del número de iteraciones n:

42

Itera- Vértices Total vér- Triángulos Total ción inserta- tices p(n) insertatriángulos dos en dos en el t(n) el exteexterior rior 1 2 0 0 4 4 3 0 0 0 4 4 20 20 48 52 5 0 20 0 52 6 32 52 80 132 7 0 52 0 132 8 56 108 144 276 9 0 108 0 276 10 104 212 272 548 ... ... ... ... ... n (*) − (*) (*) Depende si n es par o impar.

Arista más larga h(n) L √

2L/2 L/2 √ 2L/4 L/4 √ 2L/8 L/8 √ 2L/16 L/16 √ 2L/32 ... h(n−1) √ 2

Tabla 3.5: Refinamiento por iteraciones en el exterior de un sector cuadrado.

43

D

C

A

B

(a)

(b)

(c)

(d)

Figura 3.12: Refinamiento en el exterior de un sector cuadrado (iteración inicial 0, 1, 3 y 5).

p(n) =

    

3(2

n+2 2

) + 4n − 20 si n es par

si n es impar

0

(3.22)

El número de triángulos generados t(n) en función del número de iteraciones n es:

t(n) =

    

2 0

n+8 2

+ 8n − 44 si n es par

si n es impar

44

(3.23)

La arista más larga de los triángulos contenidos en el cuadrado ABCD en función del número de iteraciones n (sexta columna de la tabla 3.5) está definida por:

L

h(n) =

2

(3.24)

n−1 2

Luego se despeja n de la ecuación 3.24, obteniéndose:

n = 2 log2



L +1  

(3.25)

Finalmente se calcula el número de vértices y triángulos agregados considerando que la longitud de la arista más larga de cada triángulo dentro de ABCD sea menor o igual que un parámetro de entrada . Reemplazando la ecuación 3.25 en las ecuaciones 3.22 y 3.23 se obtiene:

p(L, ) =

    

  

t(L, ) =  

  √   6 2 L + 8 log2 L − 16 si

si

0

L  L 

  √   16 2 L + 16 log2 L − 36 si

si

0

es par es impar

L  L 

es par es impar

(3.26)

(3.27)

De las ecuaciones 3.26 y 3.27, el resultado parcial del número de vértices insertados y el número de triángulos generados específicamente en el exterior de un sector cuadrado es una función lineal de L . Y el resultado parcial del número de vértices insertados y el número de triángulos generados específicamente en 45

el interior de un sector cuadrado es una función cuadrática de L , esto según las ecuaciones 3.20 y 3.21. Considerando ambos resultados obtenidos del trabajo que se efectúa dentro y fuera de un sector cuadrado, el de mayor orden es el que se desarrolla en el interior del sector cuadrado. C. Refinamiento dentro y en el exterior de un sector cuadrado El resultado total del refinamiento realizado en el interior y en el exterior de un sector cuadrado se obtiene sumando los resultados parciales. Para el número de vértices insertados se suman las ecuaciones 3.20 y 3.26. Para el número de triángulos generados se suman las ecuaciones 3.21 y 3.27, es como sigue:

  

p(L, ) =  

  

t(L, ) =  

 2

L   2 4 L

2

 2

L   2 4 L

4

  √   + 8 2 L + 8 log2 L − 15 si

si

+1

L  L 

  √   + 16 2 L + 16 log2 L − 36 si

si

es par es impar

L  L 

es par es impar

(3.28)

(3.29)

Luego el número de vértices insertados y el número de triángulos rectángulos isósceles generados dentro y fuera de un sector cuadrado es una función cuadrática de

L . 

En el refinamiento de un sector cuadrado, el refinamiento de

los triángulos que están en el exterior es para la conformidad de la malla.

46

3.5.2.

Refinamiento de un sector cuadrado para una triangulación uniforme TRI

Teorema 3.22. En una triangulación uniforme TRI, el número de vértices insertados y el número de triángulos rectángulos isósceles generados dentro y fuera de un sector cuadrado utilizando el algoritmo Bisección-Lepp es una función cuadrática de L .

Demostración. La demostración sigue al teorema 3.21, donde el número de vértices insertados y el número de triángulos generados dentro y fuera de un sector cuadrado utilizando el algoritmo Bisección-Lepp es una función cuadrática de L , esto viene a ser un caso particular de refinamiento estable, es decir, cuando el refinamiento es local y sin el peor caso de propagación en la malla. Para generalizar este resultado se requiere demostrar que en las triangulaciones uniformes TRI no existe el peor caso de propagación. El corolario 3.6 sustenta que en una malla uniforme TRI la bisección por la arista más larga de un triángulo no tiene el peor caso de propagación.

3.6. 3.6.1.

Refinamiento de un sector circular Refinamiento de un sector circular para la triangulación TRI de la figura 3.13

Se considera el caso de refinamiento estable de una triangulación, es decir, cuando el refinamiento es local y presenta un comportamiento que sigue un patrón. Motivo por el cual se puede obtener resultados exactos. 47

Supuesto 3.23. Se consideran sólo triangulaciones conformadas por triángulos rectángulos isósceles (TRI). Definición 3.24. Triangulación inicial Tc para refinar un sector circular: La triangulación inicial Tc para refinar un sector circular es la mostrada en la figura 3.13. El refinamiento se realiza en un sector circular Φ inscrita en un cuadrado ABCD con centro P , donde se unen los vértices y ángulos internos adyacentes iguales de (cuatro) triángulos rectángulos isósceles con longitudes iniciales de hipotenusas L. Problema 3.25. Refinamiento de un sector circular: Dada una triangulación inicial Tc , un círculo Φ y un parámetro de longitud de arista , se requiere refinar el sector definido por un círculo Φ (inscrita en un cuadrado ABCD) dentro de Tc , tal que la longitud de la arista más larga de cada triángulo contenido en Φ sea menor o igual que . Teorema 3.26. Refinamiento de un sector circular: Para el problema 3.25 sobre la triangulación Tc de la definición 3.24. El número de vértices insertados y el número de triángulos rectángulos isósceles generados dentro y fuera de un sector circular utilizando el algoritmo Bisección-Lepp es una función cuadrática de L .

D

C

L

B

A

Figura 3.13: Refinamiento de un sector circular. 48

Demostración. Las triangulaciones iniciales de los refinamientos de un sector cuadrado y de un sector circular son las mismas, definidas como Ts y Tc respectivamente (figuras 3.10 y 3.13). El área del sector circular Φ está incluida en el área de un cuadrado ABCD, que es el mismo cuadrado del cual se calculado el costo de refinamiento en el teorema 3.21. Entonces, el costo de refinamiento de un sector circular es equivalente al refinamiento de un sector cuadrado (al menos en el orden de la función). Luego el número de vértices insertados y el número de triángulos rectángulos isósceles generados dentro y fuera de un sector circular utilizando el algoritmo Bisección-Lepp es una función cuadrática de L . 

3.6.2.

Refinamiento de un sector circular para una triangulación uniforme TRI

Teorema 3.27. En una triangulación uniforme TRI, el número de vértices insertados y el número de triángulos rectángulos isósceles generados dentro y fuera de un sector circular utilizando el algoritmo Bisección-Lepp es una función cuadrática de L . Demostración. La demostración sigue al teorema 3.26, donde el número de vértices insertados y el número de triángulos generados dentro y fuera de un sector circular utilizando el algoritmo Bisección-Lepp es una función cuadrática de

L , 

esto viene a ser un caso particular de refinamiento estable, es decir, cuando el refinamiento es local y sin el peor caso de propagación en la malla. Para generalizar este resultado se requiere demostrar que en las triangulaciones uniformes TRI no existe el peor caso de propagación. El corolario 3.6 sustenta que en una malla uniforme TRI la bisección por la arista más larga de un triángulo no tiene el peor caso de propagación. 49

3.7.

El peor caso de refinamiento de las triangulaciones generales TRI

El peor caso de refinamiento de las mallas conformadas de triángulos rectángulos isósceles es cuando el refinamiento de un sector R involucra el refinamiento de toda la malla (con la bisección de todos los triángulos). En este caso el refinamiento global de todos los triángulos es hasta que llegue a su estado monótono (estable) donde el refinamiento de las siguientes iteraciones son locales respecto al sector R. En la figura 3.14, el refinamiento alrededor del vértice A involucra en la primera ocasión el refinamiento (bisección) de todos los triángulos de la malla, y algunas otras hasta llegar a su estado monótono de refinamiento. Lo mismo ocurre si el refinamiento es alrededor de la arista AB y otros tipos de refinamiento local. Se nota que el refinamiento de cualquier sector que está arriba en la figura involucra el refinamiento de todos los triángulos que están en la parte inferior del mismo. Sin embargo, no todos los triángulos se bisectan en cada iteración de refinamiento del sector R, en cambio, el refinamiento es local desde que alcanza su estado monótono. Luego en cualquier tipo de refinamiento el costo de refinamiento puede incluir el peor caso. Por lo que, en general, el costo de todo refinamiento (alrededor de un vértice, arista, etc.) tiene necesariamente el término O(N), donde N es el número de triángulos de la malla inicial (antes de efectuar el refinamiento).

50

C

A

B

...

Figura 3.14: Peor caso del refinamiento de triángulos rectángulos isósceles.

3.8.

Refinamiento en una triangulación general TRI

Si el refinamiento es en una malla general TRI (no necesariamente uniforme), hay la posibilidad del peor caso de refinamiento. Entonces, en el análisis del costo considerando el peor caso, se debe agregar un término que es O(N). Donde N es el número total de triángulos de la malla inicial Mi (antes de efectuar el refinamiento).

51

Capítulo 4 Estadística experimental de la longitud de propagación del LEPP

4.1.

Introducción

La longitud de propagación del LEPP (Longest-Edge Propagation Path) de un triángulo t0 , es el número de elementos del conjunto de triángulos Lepp(t0 ) que se conforman al expandir el triángulo t0 por la arista más larga (se explica en la sección 2.2.3). Para obtener los indicadores de la longitud de propagación del LEPP en una triangulación Delaunay se realizó el siguiente procedimiento:

Generar un conjunto P de puntos aleatorios coplanares. 52

Construir una malla Γ a partir del conjunto de puntos P , utilizando el algoritmo de triangulación Delaunay. Calcular el LEPP de cada triángulo de Γ. Calcular la longitud media, máxima y desviación estándar de los LEPP de Γ.

El procedimiento descrito se aplicó a diferentes tamaños de muestras, con la finalidad de obtener resultados generales. Para obtener las medidas del LEPP (longitud media y máxima) para cada tamaño de muestra se repitió cuarenta veces los experimentos (por cada tamaño de muestra). Para los experimentos se utilizó una computadora HP (Intel Core duo) de 1.66 GHz con 1 Gb de RAM.

4.2.

Peor caso de la longitud máxima de propagación LEPP en una malla

En el peor caso la longitud máxima de propagación del LEPP en una malla de triángulos es igual al número de triángulos de la malla. Esto significa que la longitud máxima de propagación LEPP de un triángulo t0 es igual al número de elementos del conjunto Lepp(t0 ). Un ejemplo se muestra en la figura 4.1 donde la longitud máxima de propagación LEPP del triángulo t0 es igual a n + 1, que es igual al número total de triángulos de la malla (t0 , t1 , t2 , ..., tn ). El LEPP del triángulo t0 inicia arriba y se prolonga hasta el último triángulo tn , esto debido a que cada triángulo de la malla tiene su lado más largo en la parte inferior

53

con longitudes de aristas más largas crecientes según la secuencia del LEPP, es decir, Lepp(t0 ) = {t0 , t1 , t2 , ..., tn }. t0 t1

t2

t3 t4

... tn

Figura 4.1: Peor caso de la longitud máxima de propagación LEPP en una malla (con n + 1 triángulos).

4.3.

Longitud de propagación del LEPP en una malla Delaunay

4.3.1.

Longitud media de propagación del LEPP en una malla Delaunay

Se efectuó el experimento considerando los siguientes tamaños de muestra: Primero. De cien puntos hasta mil puntos. Con incrementos de cien puntos, con la finalidad de observar el comportamiento inicial. Segundo. De mil puntos hasta veinte mil puntos. Con incrementos de mil puntos. 54

En la figura 4.2 se observa que los experimentos de muestras menores a mil puntos un LEPP promedio corto, con un crecimiento proporcional al número de puntos. Desde los mil o más puntos el LEPP llega a su mayor valor donde inmediatamente se mantiene estable en un promedio (media). Longitud media del LEPP según puntos 3.8

Malla Delaunay

Longitud media del LEPP

3.7

3.6

3.5

3.4

3.3

00 20 00 19 00 18 00 17 00 16 00 15 00 14 00 13 00 12 00 11 00 10 0 90 0 80 0 70 0 60 0 50 0 40 0 30 0 20 0 10 Puntos

Figura 4.2: Longitud media de propagación del LEPP en una malla Delaunay.

Para calcular la media no se consideraron las muestras de triangulaciones construidas con menos de mil puntos debido a que el comportamiento inicial no es estable, es decir, que la media crece proporcionalmente al tamaño de la muestra. Luego, se observa que para mallas construidas con muestras mayores a mil puntos el LEPP mantiene una media de µ = 3,582 triángulos con una desviación estándar1 σ = 1,617. Una desviación estándar pequeña indica que el LEPP está alrededor y cerca de una media para triangulaciones construidas con mil o más puntos. De esta forma se confirma la existencia del LEPP promedio. En la figura 4.3 y la tabla 4.1 se observa el LEPP promedio para muestras exclusivamente 1

Desviación estándar (o desviación típica) es una medida del grado de dispersión de los datos al valor promedio. Dicho de otra manera, la desviación estándar es el promedio o variación esperada con respecto de la media aritmética.

55

Malla Delaunay Número de Puntos

1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 13000 14000 15000 16000 17000 18000 19000 20000

Lepp

3,602 3,604 3,611 3,598 3,596 3,59 3,583 3,579 3,58 3,581 3,574 3,579 3,573 3,575 3,571 3,573 3,57 3,567 3,566 3,566 Promedio: 3,582

Malla Refinada (con Lepp-Delaunay 25o )

Desviación Longitud estándar máxima del Lepp

Lepp

Desviación Longitud estándar máxima del Lepp

1,627 1,638 1,639 1,622 1,63 1,622 1,617 1,615 1,614 1,618 1,609 1,616 1,612 1,612 1,613 1,61 1,605 1,609 1,602 1,602 1,617

3,46 3,464 3,454 3,475 3,469 3,474 3,467 3,471 3,47 3,472 3,478 3,473 3,472 3,47 3,477 3,474 3,473 3,478 3,47 3,474 3,471

1,715 1,692 1,668 1,696 1,677 1,685 1,671 1,671 1,669 1,666 1,695 1,665 1,662 1,66 1,665 1,66 1,659 1,664 1,657 1,671 1,673

11,725 13,025 13,7 13,85 14,375 14,45 14,475 15,175 14,85 15,4 15,025 15,65 16,15 15,925 16,2 15,85 16,075 16,8 15,85 16,575 15,056

15,375 15,675 15,975 16,85 17,125 18,1 17,075 17,925 17,8 17,6 18,675 17,775 18,55 17,975 17,75 18 18,05 18,05 18,125 19,225 17,584

Tabla 4.1: Resultados de los experimentos realizados sobre mallas construidas por puntos.

56

mayores a mil puntos. Longitud media del LEPP según puntos 3.8

Malla Delaunay

Longitud media del LEPP

3.7

3.6

3.5

3.4

3.3

3.2

0 00 20 00 0 19 00 0 18 00 0 17 00 0 16 00 0 15 00 0 14 00 0 13 00 0 12 00 0 11 00 0 10 0 0 90 0 0 80 0 0 70 0 0 60 0 0 50 0 0 40 0 0 30 0 0 20 0 0

10

Puntos

Figura 4.3: Longitud media de propagación del LEPP en una malla Delaunay.

4.3.2.

Longitud máxima de propagación del LEPP en una malla Delaunay

En la figura 4.4 se observa el LEPP máximo de las mallas (de las mismas muestras de la sección anterior), el LEPP crece proporcionalmente al número de puntos. A partir de una cantidad de mil puntos mantiene un promedio estable de aproximadamente quince triángulos, esto se aprecia en la cuarta columna de tabla 4.1.

57

Longitud máxima del LEPP según puntos 14

Malla Delaunay

Longitud máxima del LEPP

13

12

11

10

9

8

00 20 0 0 19 0 0 18 0 0 17 0 0 16 0 0 15 0 0 14 0 0 13 0 0 12 0 0 11 0 0

0

10

0

90

0

80

0

70

0

60

0

50

0

40

0

30

0

20

10

Puntos

Figura 4.4: Longitud del LEPP máximo en una malla Delaunay.

4.4.

Longitud de propagación del LEPP en una malla refinada con Lepp-Delaunay

También se experimentó con mallas refinadas con el algoritmo Lepp-Delaunay que se emplea para mejorar las mallas hasta que el ángulo mínimo de los triángulos sean mayores o iguales que 25 grados sexagesimales. Este algoritmo se aplicó sobre las mismas mallas de la sección anterior, por lo tanto las muestras son las mismas.

58

4.4.1.

Longitud media de propagación del LEPP en una malla refinada con Lepp-Delaunay Longitud media del LEPP según puntos 3.8

Malla Delaunay Malla refinada (con Lepp−Delaunay 25)

Longitud media del LEPP

3.7

3.6

3.5

3.4

3.3

00 20 0 0 19 0 0 18 0 0 17 0 0 16 0 0 15 0 0 14 0 0 13 0 0 12 0 0 11 0 0

0

10

0

90

0

80

0

70

0

60

0

50

0

40

0

30

0

20

10

Puntos

Figura 4.5: Longitud media de propagación del LEPP en una malla refinada con Lepp-Delaunay.

Para calcular la media no se consideraron las muestras de triangulaciones construidas con menos de mil puntos. Se observa que para cantidades grandes (mayores a mil puntos) el LEPP mantiene una media de µ = 3,471 triángulos (menor a la malla Delaunay no refinada µ = 3,582) y una desviación estándar 1,673. Una desviación estándar pequeña indica que el LEPP está alrededor y cerca de una media. De esta manera se confirma la existencia del LEPP promedio. En la figura 4.6 se presenta el LEPP promedio para muestras exclusivamente mayores a mil puntos, donde la barra sombreada (de color negro) representa las mallas refinadas con el algoritmo Lepp-Delaunay(25). Los valores de las medias y las desviaciones estándar de cada tamaño de muestra están en la quinta y sexta columna de la tabla 4.1.

59

La reducción del LEPP promedio respecto a la malla inicial no refinada se explica al efecto de la aplicación del algoritmo Lepp-Delaunay(25) que mejora la calidad de los triángulos, y en consecuencia la longitud media del LEPP es menor. Longitud media del LEPP según puntos 3.8

Malla Delaunay Malla refinada (con Lepp−Delaunay 25)

Longitud media del LEPP

3.7

3.6

3.5

3.4

3.3

3.2

0 00 20 00 0 19 00 0 18 00 0 17 00 0 16 00 0 15 00 0 14 00 0 13 00 0 12 00 0 11 00 0 10 0 0 90 0 0 80 0 0 70 0 0 60 0 0 50 0 0 40 0 0 30 0 0 20 0 0

10

Puntos

Figura 4.6: Longitud media de propagación del LEPP en una malla refinada con Lepp-Delaunay.

60

4.4.2.

Longitud máxima de propagación del LEPP en una malla refinada con Lepp-Delaunay Longitud máxima del LEPP según puntos

Longitud máxima del LEPP

18

Malla Delaunay Malla refinada (con Lepp−Delaunay 25)

16

14

12

10

8

00 20 0 0 19 0 0 18 0 0 17 0 0 16 0 0 15 0 0 14 0 0 13 0 0 12 0 0 11 0 0

0

10

0

90

0

80

0

70

0

60

0

50

0

40

0

30

0

20

10

Puntos

Figura 4.7: Longitud del LEPP máximo en una malla refinada con LeppDelaunay.

En la figura 4.7 las barras sombreadas (de color negro) representan la longitud máxima del LEPP de las mallas refinadas con el algoritmo LeppDelaunay(25) construidas con las mismas muestras de la sección 4.3.2, en la que se muestra la longitud máxima del LEPP de las mallas sin refinamiento. Los resultados para muestras mayores a mil puntos se presentan en la séptima columna de la tabla 4.1 con un promedio de 17,584 triángulos.

61

4.5.

Nuevo algoritmo de refinamiento: Lepp-BisecciónDelimitado

La crítica fundamental que se puede hacer al algoritmo Lepp-Bisección es el peor caso en donde la propagación del LEPP llega a abarcar incluso toda la malla. En razón a que la longitud de propagación del LEPP tiene una media pequeña y considerando que también se dispone de las estadísticas de la longitud máxima del LEPP para cada tamaño de muestra. En esta sección se elabora y plantea un nuevo algoritmo de refinamiento denominado Lepp-Bisección-Delimitado, sin el peor caso de propagación. En esencia es una condición que se agrega a su predecesor. En la búsqueda del LEPP se controla el número de triángulos que se avanza, si este pasa un límite Max entonces se bisecta el triángulo que está en el límite y dejamos de avanzar en la búsqueda del último par de triángulos (o triángulo que está en el perímetro). El triángulo que cae en el límite es el triángulo con la arista más larga de toda la secuencia examinada de triángulos (de acuerdo a las propiedades del LEPP) por lo puede ser bisectado. El inconveniente por supuesto es dejar de buscar el último triángulo tn del LEPP. Si se considera los experimentos efectuados a partir de los diferentes tamaños de muestra, sobre las triangulaciones Delaunay refinadas o sin refinar en ningún de los casos el LEPP máximo es mayor a 20 (tabla 4.1) por lo que el límite apropiado de búsqueda es Max = 20 (u otro si la aplicación lo exige). También se respalda por el estudio teórico en el cual se tiene una media de cuatro triángulos y una desviación estándar de 2,4.

62

Por otro lado, tratándose de refinamiento de un sector, el efecto de la inclusión de un límite en la búsqueda del LEPP no tiene importancia debido a que los triángulos que pasan el límite pueden no estar en la región de refinamiento, y si están pueden ser bisectados cuando se examina otro triángulo de la región de refinamiento. Dentro de los algoritmos de ordenamiento más utilizados esta el Quicksort que en el caso promedio es óptimo pese a que tiene el peor caso (no frecuente). El peor caso en las mallas de triángulos es aun menos frecuente, por lo que es posible que casi nunca se llegue al límite (al menos en los experimentos con mallas elaboradas por vértices aleatorios). En el nuevo algoritmo de refinamiento basado en la bisección de triángulos por la arista más larga, el costo de la búsqueda del LEPP de un triángulo t0 es constante O(1), no depende del tamaño de la malla (número de triángulos o vértices de la triangulación).

63

Capítulo 5 Estadística teórica de la longitud de propagación del LEPP

5.1.

Introducción a las funciones generatrices

Esta sección tiene la finalidad de recordar los conceptos relacionados con las funciones generatrices y, primordialmente, establecer la terminología y notación para las mismas (hay textos de referencia por ejemplo [5]). Con igual intención se ha incluido en la sección de anexos el tema de probabilidades discretas. Las funciones generatrices vienen a ser un método simbólico. El de mayor utilidad que se conoce para tratar con secuencias de números. Se utilizan, por ejemplo, para resolver problemas combinatorios entre otros varios. Se aplican en diferentes áreas de la ciencia. La función generatriz tiene la siguiente forma:

64

G(z) = g0 + g1 z + g2 z 2 + · · · =

X

gn z n

(5.1)

n≥0

Se dice que G(z) es la función generatriz para la secuencia < g0 , g1 , g2 , . . .>, el cual también se denomina < gn >. Hay dos tipos de “forma cerrada” para las funciones generatrices. Puede haber una forma cerrada para G(z), expresada en términos de z; o puede haber una forma cerrada para gn , expresado en términos de n. Por ejemplo, la función generatriz para los “números Fibonacci” tiene la forma cerrada z/(1 − z − z 2 ) y √ los números Fibonacci tienen la forma cerrada (φn − φˆn )/ 5.

5.2.

Función generatriz de probabilidad

Si X es una variable aleatoria que toma solamente valores de enteros no negativos, la función generatriz de probabilidad o FGP de X es:

Gx (z) =

X

P r(X = k)z k

(5.2)

k≥0

Esta serie de potencias en z contiene toda la información acerca de la variable aleatoria X. Los coeficientes de Gx (z) son no negativos y su sumatoria es uno, es decir:

Gx (1) = 1 65

(5.3)

La ventaja de las funciones generatrices de probabilidad es que usualmente simplifican el cálculo de medias y varianzas. La media (promedio o valor esperado) se expresa como:

E(x) = =

P

P

k≥0 k.P r(X

= k)

k≥0 k.P r(X

= k).k.z k−1 |z=1

= G0x (1)

(5.4)

Es decir, se diferencia la FGP con respecto a z y se asigna z = 1. La varianza es como sigue:

E(X 2 ) = =

P

P

k≥0 k

2

.P r(X = k)

k≥0 P r(X





= k). k(k − 1)z k−2 + kz k−1

z=1

= G00X (1) + G0X (1)

Por lo tanto:

V (X) = G00X (1) + G0X (1) − G0X (1)2

(5.5)

Las ecuaciones (5.4) y (5.5) indican que se puede calcular la media y la varianza si se puede calcular los valores de las dos derivadas, G0X (1) y G00X (1).

66

5.3.

Longitud media de propagación del LEPP

En esta sección se calcula la longitud media de propagación LEPP utilizando funciones generatrices de probabilidad. En una malla conforme de triángulos, cada triángulo Ti tiene tres lados TiA ,TiB y TiC en orden creciente de longitud respectivamente, donde, el lado más corto es TiA y el lado más largo es TiC . Se dan dos casos particulares cuando los triángulos tienen dos o tres lados iguales (triángulo isósceles y triángulo equilátero respectivamente). Definición 5.1. Triángulo vecino de tipo A, B y C del LEPP: Sean Ti y Ti+1 triángulos vecinos de la lista ordenada del Lepp(T0 )1 , donde Ti es vecino de Ti+1 por el lado más largo de Ti (es decir por TiC ), entonces:

Se dice que Ti+1 es vecino de “tipo A” si Ti+1 es vecino de Ti por el lado más corto de Ti+1 , es decir, por T(i+1)A . Se dice que Ti+1 es vecino de “tipo B” si Ti+1 es vecino de Ti por el lado medio de Ti+1 , es decir, por T(i+1)B . Se dice que Ti+1 es vecino de “tipo C” si Ti+1 es vecino de Ti por el lado más largo de Ti+1 , es decir, por T(i+1)C . Teorema 5.2. Longitud media de propagación del LEPP: La longitud media de propagación del LEPP de un triángulo es cuatro.

Demostración. El conjunto Lepp(T0 ) proviene de una secuencia ordenada de triángulos. El número de elementos está compuesto de tres partes: (a) Un triángulo inicial T0 sin tipo debido a que el primer triángulo no tiene predecesor. (b) 1

Que cumplen las propiedades del LEPP definida en la sección 2.2.3.

67

Seguido indistintamente de cero o más triángulos de tipo A o B, y (c) termina con un triángulo Tn de tipo C. Luego la longitud mínima del LEPP es dos (compuesta del primer triángulo sin tipo y el último triángulo de tipo C). Número medio de triángulos de tipo B o C del LEPP: Sean:

p = Probabilidad de tener un triángulo vecino de tipo C (de que el siguiente triángulo es vecino por su lado más largo). q = Probabilidad de tener un triángulo vecino de tipo A o B (de que el siguiente triángulo es vecino por su lado más corto o lado medio).

En una malla de triángulos el número de lados cortos, medios y largos son iguales2 . Por lo que es justo asignar la probabilidad de gulo vecino. Luego: p =

1 3

q=

2 3

1 3

a cada tipo de trián-

(q representa dos posibilidades).

La función generatriz de probabilidad del número de triángulos de la secuencia de vecinos de tipo A o B hasta tener un vecino de tipo C está dado por:

G(z) = p + qpz + q 2 pz 2 + · · · = p

X

(qz)n

(5.6)

k≥0

Y su forma cerrada es:

G(z) = 2

p 1 − qz

(5.7)

Para cualquier triángulo Ti del LEPP. El triángulo vecino Ti+1 comparte cualquiera de sus tres lados con igual probabilidad P (Ti+1A ) = P (Ti+1B ) = P (Ti+1C ) = 13 .

68

Si se deriva (5.7) se obtiene:

pq (1 − qz)2

(5.8)

00

2pq 2 G (z) = (1 − qz)3

(5.9)

2q 2 . p2

Luego la media y varianza del número medio

G0 (z) =

De esto G0 (1) =

q p

y G00 (1) =

de triángulos de tipo B o C es:

E(G) = G0 (1) =

q =2 p

V (G) = G00 (1) + G0 (1) − G0 (1)2 =

(5.10)

q =6 p2

(5.11)

Al resultado de la ecuación (5.10) se le debe sumar dos, esto al considerar la parte (a) y (c) del número de elementos del LEPP descrito inicialmente en la presente demostración. Finalmente la longitud media de propagación del LEPP por el lado más largo de un triángulo es cuatro.

Observación: La función generatriz de probabilidad de la ecuación (5.7) es equivalente a la expresión regular G(z) = (qz)∗ p.

69

5.4.

Desviación estándar de la longitud media de propagación del LEPP

Dado la varianza de la longitud media de propagación del LEPP en la ecuación (5.11), la correspondiente desviación estándar (denotado por σ) es:

σ=

5.5.

q

V (G) =

√

6 = 2,449

(5.12)

Comparación de los resultados empíricos y teóricos de la longitud media de propagación del LEPP

En la sección (4.3.1) se realizó un estudio empírico (experimental) sobre la longitud del LEPP. Para cada tamaño de muestra, se construyó la triangulación Delaunay. La longitud media de propagación del LEPP es el número promedio de elementos del conjunto Lepp(t0 ) (que se conforman al expandir el triángulo t0 por la arista más larga). Esta longitud media del LEPP es para todos los casos menor que el valor teórico de cuatro triángulos (es aproximadamente igual a µ = 3,6 triángulos). En la anterior sección (5.3) se efectuó el cálculo teórico de la longitud media de propagación del LEPP, obteniéndose cuatro triángulos. La diferencia puede deberse a que en el estudio empírico (el experimento):

70

Se efectuó en una malla construida con el criterio Delaunay, que es la triangulación más equilátera. Se ha calculado el LEPP promedio considerando todos los triángulos de la malla incluido los casos especiales: Triángulos con la arista más larga en el perímetro (borde) de la malla, cuyo Lepp es uno; y triángulos cuyo Lepp termina en un triángulo con la arista más larga en el perímetro (borde) de la malla. Por naturaleza, en los experimentos empíricos difícilmente se termina con una misma media. Los cálculos con las funciones generatrices considera eventos estrictamente independientes (en condiciones ideales).

Al menos estos factores hacen que el valor del LEPP promedio del experimento empírico sea menor al teórico. Debido a que los resultados son aproximados se confirma la existencia de la longitud media del LEPP. También ambos resultados indican que este valor en promedio es pequeño.

5.6.

Cuando en el LEPP las probabilidades de tener un triángulo vecino de tipo A, B y C son distintas

El conjunto Lepp(T0 ) tiene una secuencia ordenada de triángulos de tipo A, B y C con excepción del primero que no tiene tipo. En la demostración del teore71

ma 5.2 se ha considerado que las probabilidades de tener un vecino de tipo A, B o C son las mismas (con equiprobabilidades de 13 ). También se tuvo: p = Probabilidad de tener un triángulo vecino de tipo C (de que el siguiente triángulo es vecino por su lado más largo). q = Probabilidad de tener un triángulo vecino de tipo A o B (de que el siguiente triángulo es vecino por su lado más corto o lado medio).

Donde: p =

1 3

q=

2 3

(q representa dos posibilidades).

Pero ¿qué sucedería si la probabilidad de p, que es la probabilidad de tener un triángulo vecino de tipo C, fuera distinta? La probabilidad de tener un vecino de tipo A, B y C no siempre son iguales, depende de cada malla. Por ejemplo, se tiene el caso especial de la malla de la figura 4.1 donde la probabilidad de tener un vecino de tipo C es cero (p = 0), en esta malla no existe vecinos de tipo C debido a que el LEPP de cada triángulo siempre termina en el borde de la malla, es decir, el último triángulo de cada LEPP es tn (cuyo lado más largo está en el borde de la malla). Entonces si se cambia adecuadamente la probabilidad de tener un vecino de tipo C, por ejemplo, en el caso particular cuando se asume p = 0,3872. Primero la probabilidad de q (que es igual a 1 − p) cambia a q = 0,6128. También se modifican los resultados de la demostración de teorema 5.2. Se vuelve a calcular la media y varianza del número medio de triángulos de tipo B o C, con el siguiente resultado:

E(G) = G0 (1) =

q = 1,582644628 p

72

(5.13)

V (G) = G00 (1) + G0 (1) − G0 (1)2 =

q = 4,087408647 p2

(5.14)

Al resultado de la ecuación (5.13) se le debe sumar dos. Luego longitud media de propagación del LEPP por el lado más largo de un triángulo es 3,582644628 triángulos. Este resultado es aproximadamente igual al resultado obtenido en los experimentos (se diferencia en 0,000644628). Del mismo modo, dado la varianza de la longitud media de propagación del LEPP en la ecuación (5.14), la desviación estándar es:

σ=

q

V (G) =

√

6 = 2,021734069

(5.15)

También en este caso los valores empíricos son menores al valor teórico (la diferencia de los dos resultados es 0,404734069). Estos resultados se presentan en la tercera columna de la tabla (5.1) como sigue: Resultado

Experimento empírico

Longitud media Desviación estándar

3,582 1,617

Funciones generatrices con equiprobabilidad en los vecinos de tipo A, B y C 4 2,449

Funciones generatrices con probabilidad p = 0,3872 en el vecino de tipo C 3,582644628 2,021734069

Tabla 5.1: Resultados de la longitud media y desviación estándar de la propagación del LEPP.

Los resultados del experimento empírico son aproximadamente iguales a las obtenidas con las funciones generatrices, pero asumiendo distintas probabili73

dades para los vecinos de tipo A, B y C (específicamente con p = 0,3872 que es la probabilidad de tener un vecino de tipo C).

74

Capítulo 6 Conclusiones 1. El problema de refinamiento de mallas compuestas de triángulos rectángulos isósceles es: Dada una triangulación uniforme inicial Mi de triángulos rectángulos isósceles, una región de refinamiento R de Mi y un parámetro de longitud de arista ; obtener una triangulación refinada1 y conforme Mf de triángulos rectángulos isósceles, tal que la longitud de la arista más larga de cada triángulo de Mf que intersecta R sea menor o igual que . Se demostró que el refinamiento de la región R depende de la condición de refinamiento: En el refinamiento alrededor de un vértice P , la inserción de puntos y generación de triángulos es una función logarítmica de L . En el refinamiento alrededor de una arista (segmento) AB, la inserción de puntos y generación de triángulos es una función lineal de L . La inserción de puntos y generación de triángulos para el refinamiento de un sector cuadrado es una función cuadrática de L . 1

Insertando puntos y generando nuevos triángulos rectángulos isósceles por efecto de la bisección iterativa de los mismos.

75

Donde L es la longitud inicial de la arista más larga de los triángulos que intersectan R y  es la cota de la longitud de arista más larga a la cual se deben reducir todos los triángulos que intersectan R. 2. En la estudio teórico, la longitud media de propagación del LEPP es igual a cuatro triángulos. Resultado obtenido utilizando funciones generatrices de probabilidad. Si se reajusta adecuadamente la probabilidad de tener un vecino de tipo C, por ejemplo, con p = 0,3872, la longitud media de propagación del LEPP es µ = 3,5826 triángulos. 3. En el estudio empírico, la longitud media de propagación del LEPP es menor que cuatro triángulos para todos los casos, lo cual está en concordancia con el valor teórico (para muestras aleatorias mayores a mil vértices la media es igual a µ = 3,582 triángulos con una desviación estándar σ = 1,617).

76

ANEXO A Probabilidades discretas Las probabilidades se denominan “discretas” si se puede calcular las probabilidades de todos los eventos mediante sumatorias en lugar de integraciones. Sea Ω un espacio de probabilidad, es decir, el conjunto de todos los eventos que pueden ocurrir a un problema dado, con una regla que asigna una probabilidad Pr(ω) a cada evento ω ∈ Ω. La probabilidad Pr(ω) debe ser un número real no negativo, con la siguiente condición: X

Pr(ω) = 1

ω∈Ω

Cada valor Pr(ω) debe estar en el intervalo [0. .1]. Se dice a Pr una distribución de probabilidad, porque distribuye el total de probabilidades (que es uno) entre los eventos ω. Valor esperado: Es la media de una variable aleatoria X sobre un espacio de probabilidad Ω. E(X) =

X

X(ω) Pr(ω)

(1)

ω∈Ω

Propiedades: Si X y Y son dos variables aleatorias definidas en el mismo espacio de probabilidad y si α es una constante: E(X + Y ) =

X



X(ω) + Y (ω) Pr(ω) = E(X) + E(Y )

ω∈Ω

E(αX) = αE(X)

E(XY ) = E(X)E(Y ),

Si X y Y son variables aleatorias independientes.

Varianza: Se define como: 

V (X) = E (X − E(X))2



(2)

Si se denota µ en lugar de E(X), la varianza V (X) es el valor esperado de (X − µ)2 . Esto mide la “dispersión” de X. Hay una forma de calcular la varianza en lugar de la ecuación (2), teniendo en cuenta que E(X) es una constante. 77

V (X) = E(X 2 ) − (E(X))2

(3)

“La varianza es la media de los cuadrados menos el cuadrado de la media”. Desviación estándar: Es la raíz cuadrada de la varianza, y usualmente se denota por la letra Griega σ: σ=

q

V (X)

78

(4)

Bibliografía [1] L. Paul Chew. Guaranteed-quality mesh generation for curved surfaces. In SCG ’93: Proceedings of the ninth annual symposium on Computational geometry, pages 274–280, New York, NY, USA, May 1993. ACM. [2] Mark de Berg, Marc van Kreveld, Mark Overmars, and Orfried Schwarzkopf. Computational Geometry Algorithms and Applications. Springer-Verlang Berlin Heidelberg, 1997, 2000. [3] Mark Duchaineau, Murray Wolinsky, David E. Sigeti, Mark C. Miller, Charles Aldrich, and Mark B. Mineev-Weinstein. ROAMing terrain: realtime optimally adapting meshes. In VIS ’97: Proceedings of the 8th conference on Visualization ’97, pages 81–88, Los Alamitos, CA, USA, 1997. IEEE Computer Society Press. [4] Jacob E. Goodman and Joseph O’Rourke. Handbook of Discrete and Computational Geometry. Discrete Mathematics and Its Applications. CRC Press LLC, 1997. [5] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1994. [6] Claudio Gutierrez, Flavio Gutierrez, and María-Cecilia Rivara. Complexity of the bisection method. Theor. Comput. Sci., 382(2):131–138, 2007. [7] María-Cecilia Rivara. Algorithms for refining triangular grids suitable for adaptative and multigrid techniques. International Journal of Numerical Methods in Engineering, 20:745–756, 1984. [8] María-Cecilia Rivara. Local modification of the meshes for adaptative and/or multigrid finite-element methods. Journal of Computational and Applied Mathematics, 36:79–89, 1991.

79

[9] María-Cecilia Rivara. New longest-edge algorithm for the refinement and/or improvement of unstructured triangulation. International Journal of Numerical Methods in Engineering, 40:3313–3324, 1997. [10] María-Cecilia Rivara and Gabriel Iribarren. The 4-Triangles longest-side partition of triangles and linear refinement algorithms. Mathematics of Computing, 65(216):1485–1502, 1996. [11] María-Cecilia Rivara and Cristian Levin. A 3D refinement algorithm suitable for adaptative and multi-grid techniques. Comunications in Applied Numerical Methods, 8:281–290, 1992. [12] María-Cecilia Rivara and Mauricio Palma. New LEPP algorithms for quality polygon and volume triangulation: Implementation issues and practical behavior. The 1997 Joint ASME/ASCE/SES Summer Meeting. Northwestern University. Evanston Illinois, June 29 - July 2 1997. [13] María-Cecilia Rivara and M. J. Vénere. Cost analysis of the longest-side (triangle bisection) refinement algorithm for triangulation. Engineering with Computers, 12(3-4):224–234, September 1996. [14] Maria-Cecilia Rivara and Carlo Calderon. Lepp terminal centroid method for quality triangulation. Computer-Aided Design, November 2008. [15] Maria-Cecilia Rivara, Nancy Hitschfeld, and Bruce Simpson. Terminaledges Delaunay (small-angle based) algorithm for the quality triangulation problem. Computer-Aided Design, 33(3):263–277, March 2001. [16] Ivo G. Rosenberg and Frank Stenger. A lower bound on the angles of triangles constructed by bisecting the longest side. Mathematics of Computation, 29(130):390–395, 1975. [17] Jim Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algorithms, 18(3):548–585, 1995. [18] Jonathan Richard Shewchuk. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In FCRC ’96/WACG ’96: Selected papers from the Workshop on Applied Computational Geometry, Towards Geometric Engineering, pages 203–222, London, UK, 1996. SpringerVerlag. [19] Jonathan Richard Shewchuk. Delaunay Refinement Mesh Generation. PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1997. Available as Technical Report CMU-CS-97-137. 80

[20] Jonathan Richard Shewchuk. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry: Theory and Applications, 22:1–3, May 2002.

81