Subdivisão Econômica 3-Colorível de uma Triangulação Esférica

Abstract: We describe an algorithm to subdivide an arbitrary triangulation of the sphere to produce a triangulation that is vertex-colorable with three colors. (Three-colorable triangulations can be efficiently represented and manipulated by the ``gem'' data structure of Montagner and Stolfi.) The standard solution to this problem is the barycentric subdivision, which produces $6n$ triangles when applied to a triangulation with $n$ faces. Our algorithm eliminates all vertices of odd degree (which are the only obstacles to 3-colorability) in pairs, by bisecting only a few triangles at a time. While our algorithm has an exponential worst-case upper bound, it is expected to produce between $n$ and $2n$ triangles in typical cases.



Resumo: Descrevemos um algoritmo para subdividir uma triangulação arbitrária da esfera de modo a produzir uma triangulação que é colorível nos vértices com três cores. (Triangulações 3-coloríveis podem ser eficientemente representadas e manipuladas pela estrutura de dados ``gema'' de Montagner e Stolfi.) A solução usual para este problema é a subdivisão baricêntrica, que produz $6n$ triângulos quando aplicada a uma triangulação com $n$ faces. Nosso algoritmo elimina todos os vértices de grau ímpar (que são os únicos obstáculos para 3-coloração) aos pares, bissectando apenas alguns triângulos de cada vez. Embora nosso algoritmo tenha apenas um limitante superior de pior caso exponencial, espera-se que ele produza entre $n$ e $2n$ triângulos em casos típicos.

2012