Empacotamento de Discos sem Sobreposição na Triangulação de Malhas Não Obtusas

Resumo

As malhas triangulares são usadas em muitas aplicações importantes relacionadas à forma, incluindo modelagem geométrica, simulações numéricas, produção de animação, simulação de sistema e visualização. No entanto, essas malhas são normalmente geradas com diversos defeitos e elementos de baixa qualidade, dificultando sua aplicação prática. Um estudo analítico e numérico sobre a triangulação de regiões poligonais de n vértices (podendo conter buracos) de modo que nenhum ângulo na triangulação final meça mais que π/2 usando um método de empacotamento de discos sem sobreposição foi desenvolvido com base nos resultados teóricos e nos exemplos apresentados por alguns métodos computacionais atuais. O estudo tem como ponto de partida o trabalho de Bern et al. [2], no qual é desenvolvido um algoritmo baseado em empacotamento de discos, uma poderosa técnica geométrica útil em uma variedade de contextos. Nesse método, antes de construir uma malha, preenche-se o domínio com círculos, compactados de forma que as lacunas entre eles sejam circundadas por três ou quatro círculos tangentes. (Acondicionamentos de círculos com apenas lacunas de três lados formam uma espécie de análogo discreto para mapeamentos conformes [10]. No entanto, para a maioria dos domínios, algumas lacunas de quatro lados são necessárias e, em algumas situações, as lacunas de quatro lados são realmente úteis, pois levam a vértices de grau 4 na malha.) Em seguida, usa-se esses círculos como uma estrutura para construir a malha, colocando os vértices da malha nos centros dos círculos, pontos de tangência e dentro de cada lacuna. O trabalho demonstra, de maneira construtiva, o teorema que diz que qualquer região poligonal com ou sem buracos de n vértices pode ser triangulada com O(n) triângulos retângulos. Esse método de empacotamento de discos é uma etapa da demonstração, construtiva, de que toda superfície poliédrica admite triangularização própria aguda realizada por Maehara [6]. Na sequência, o estudo se concentra em alguns aspectos da relação do empacotamento de discos com mapeamentos conformes, mais especificamente em algumas dificuldades práticas e numéricas dos problemas de empacotamento de discos, um problema conhecido por ser NP-difícil [4]. Na geometria Riemanniana, o empacotamento de discos de triangulações está intimamente ligado ao Teorema de Mapeamento de Riemann, que afirma que existe um mapeamento conforme (preservando o ângulo) entre dois conjuntos abertos simplesmente conectados no plano. Thurston havia conjecturado que empacotamentos de discos podem ser usados para construir mapas conformes aproximados; isso foi provado mais tarde por Rodin e Sullivan [8], que formou a base de um extenso trabalho em mapeamentos conformes discretos [3] e funções analíticas. Uma excelente exposição de alto nível desta direção de pesquisa é dada por Stephenson [9]. Nas últimas décadas, diferentes técnicas de otimização e geração de malha triangular foram apresentadas, entretanto, a maioria dos métodos existentes foram analisados empiricamente e não têm comprovação teórica [5]. Um exemplo de alternativa com maior embasamento teórico na busca na otimização de malhas em relação aos ângulos, é o desenvolvido de métodos baseados em mapeamentos conformes [5] usando empacotamento de discos [11]. O que pode não ser tão fácil computacionalmente, pois muitos dos resultados teóricos sobre empacotamento de discos dependem essencialmente de cálculos no computador. Estudos recentes demonstram, por exemplo, a necessidade do uso de aritmética intervalar para trabalhar com números reais não representáveis na memória do computador e para verificar desigualdades em conjuntos de valores incontáveis, mas compactos [1, 7]. Outra opção, vislumbrada aqui como trabalhos futuros, será utilizar os passos construtivos utilizados por Maehara [6] como base para um método de construção de malha aguda com sólida base teórica. Apesar de teoremas garantirem a existência de malhas triangulares agudas e não obtusas com número finito de elementos, os métodos numéricos atuais falham em alguns casos práticos. Este trabalho identifica, algumas lacunas entre a teoria (baseada no conjunto dos números reais) e a implementação computacional (limitada pela aritmética de ponto flutuante), analisando especificamente como os erros numéricos afetam, por exemplo, sequências iterativas, comparações geométricas essenciais para a geração de malhas, entre outros. [...]