Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
TRANSVERSAIS DE TRIANGULOS E SUAS APLICACOES EM
TRIANGULACOES
Vicente Helano Feitosa Batista
Tese de Doutorado apresentada ao Programa
de Pos-graduacao em Engenharia Civil,
COPPE, da Universidade Federal do Rio
de Janeiro, como parte dos requisitos
necessarios a obtencao do tıtulo de Doutor
em Engenharia Civil.
Orientadores: Fernando Luiz Bastos Ribeiro
Fabio Protti
Rio de Janeiro
Dezembro de 2010
TRANSVERSAIS DE TRIANGULOS E SUAS APLICACOES EM
TRIANGULACOES
Vicente Helano Feitosa Batista
TESE SUBMETIDA AO CORPO DOCENTE DO INSTITUTO ALBERTO LUIZ
COIMBRA DE POS-GRADUACAO E PESQUISA DE ENGENHARIA (COPPE)
DA UNIVERSIDADE FEDERAL DO RIO DE JANEIRO COMO PARTE DOS
REQUISITOS NECESSARIOS PARA A OBTENCAO DO GRAU DE DOUTOR
EM CIENCIAS EM ENGENHARIA CIVIL.
Examinada por:
Prof. Fernando Luiz Bastos Ribeiro, D.Sc.
Prof. Fabio Protti, D.Sc.
Prof. Jose Antonio Fontes Santiago, D.Sc.
Prof. Luerbio Faria, D.Sc.
Prof. Guilherme Dias da Fonseca, Ph.D.
RIO DE JANEIRO, RJ – BRASIL
DEZEMBRO DE 2010
Batista, Vicente Helano Feitosa
Transversais de Triangulos e suas Aplicacoes em
Triangulacoes/Vicente Helano Feitosa Batista. – Rio de
Janeiro: UFRJ/COPPE, 2010.
XIV, 79 p.: il.; 29, 7cm.
Orientadores: Fernando Luiz Bastos Ribeiro
Fabio Protti
Tese (doutorado) – UFRJ/COPPE/Programa de
Engenharia Civil, 2010.
Referencias Bibliograficas: p. 71 – 79.
1. Transversal de triangulos. 2. Estrutura de
dados. 3. Triangulacao de Delaunay. 4. Vigilancia
em Terrenos. I. Ribeiro, Fernando Luiz Bastos et al.
II. Universidade Federal do Rio de Janeiro, COPPE,
Programa de Engenharia Civil. III. Tıtulo.
iii
Aos meus queridos pais, Joao e
Maria, e a minha magnıfica
esposa, Ledjane.
iv
Agradecimentos
Meus orientadores, Fernando e Fabio, os quais foram protagonistas da historia de
minha formacao, detem grande parte dos meritos desta tese. Trabalho com o Prof.
Fernando desde o mestrado. Foi ele quem me apresentou ao verdadeiro mundo
interdisciplinar da COPPE. Sao engenheiros fazendo matematica, matematicos fa-
zendo engenharia, quımicos, fısicos, geologos, etc. Encontramos os mais diversos
profissionais atuando em diversas areas da ciencia e tecnologia. Isto me possibilitou
ingressar no lindo campo da geometria computacional. Ao professor Fabio, devo
minha gratidao por ter confiado em mim, pelas frutuosas reunioes e pelas palavras
de incentivo nos momentos certos.
Ao professor Sylvain Pion, que foi meu coordenador durante o perıodo sanduıche
na Franca. Agradeco tambem a Johannes Singler e David L. Millman, pela oportu-
nidade de trabalhar em conjunto sobre algoritmos geometricos paralelos.
A Luerbio e Guilherme, por terem aceitado participar da banca examinadora
desta tese.
A minha esposa, Ledjane, por ser ela, magnıfica; fundamental em minha vida.
Aos meus pais, Joao Batista e Maria Feitosa, que dedicaram suas vidas a
educacao de seus filhos.
A minha irma, Helana, e meu querido e unico sobrinho, Joao Amadeu.
A George, meu grande amigo de doutorado, parceiro em tudo.
Aos meus compadres, Marco e Paula Colbachini, por terem me acolhido em sua
casa durante meus ultimos meses no Rio de Janeiro.
Aos professores Jose Santiago e Robertinho por terem sido meus mestres.
v
A todos os amigos que adquiri ao longo destes ultimos anos na COPPE.
O presente trabalho foi redigido utilizando a classe de documentos coppe, per-
tencente ao projeto CoppeTEX, o qual tenho o prazer de coordenar junto com meu
amigo George e o professor Paulo Laranjeira.
Mesmo com a fe por vezes abalada, como um bom (ou mal) pecador que sou,
sempre tive a companhia de Deus. Entrego minha alma Aquele de onde acredito
que provem todas as coisas.
Esta tese foi realizada com o apoio financeiro do Conselho Nacional de Desen-
volvimento Cientıfico e Tecnologico (CNPq) do Brasil.
vi
Resumo da Tese apresentada a COPPE/UFRJ como parte dos requisitos necessarios
para a obtencao do grau de Doutor em Ciencias (D.Sc.)
TRANSVERSAIS DE TRIANGULOS E SUAS APLICACOES EM
TRIANGULACOES
Vicente Helano Feitosa Batista
Dezembro/2010
Orientadores: Fernando Luiz Bastos Ribeiro
Fabio Protti
Programa: Engenharia Civil
O objetivo principal desta tese e obter uma estrutura de dados capaz de represen-
tar triangulacoes bidimensionais, diminuindo a redundancia no armazenamento das
informacoes topologicas, sem causar impactos excessivos na velocidade de acesso as
informacoes subjacentes. Esta estrutura e baseada em vertices, ou seja, as arestas e
faces sao representadas apenas de modo implıcito. Antes de apresentarmos a estru-
tura em si, consideramos o problema de calcular transversais de triangulos mınimos,
tanto por vertice, quanto por aresta. A complexidade computacional das versoes
de decisao associadas a estes problemas e demonstrada para o caso de grafos pla-
nares e maximais planares. Para os transversais por vertice, apresentamos tambem
quatro algoritmos acompanhados de seus resultados experimentais. Demonstramos
ainda dois teoremas sobre a complexidade do problema de vigilancia em terrenos.
Ao final, descrevemos a interface da estrutura implementada e sua utilizacao em
um algoritmo de construcao de triangulacoes de Delaunay. Os resultados demons-
tram que, em media, e possıvel reduzir em 12% o numero de referencias utilizadas,
mantendo sua performance compatıvel com a de estruturas do mesmo tipo.
vii
Abstract of Thesis presented to COPPE/UFRJ as a partial fulfillment of the
requirements for the degree of Doctor of Science (D.Sc.)
TRIANGLE TRANSVERSALS AND THEIR APPLICATIONS TO
TRIANGULATIONS
Vicente Helano Feitosa Batista
December/2010
Advisors: Fernando Luiz Bastos Ribeiro
Fabio Protti
Department: Civil Engineering
The aim of this thesis is to design a data structure for representing planar tri-
angulations decreasing the amount of redundancy of combinatorial data, without
incurring excessive speedowns to the access of the underlying information. This
structure is based on vertices in the sense that edges and faces are only implicitly
represented. Before presenting our structure, we consider the problem of computing
minimum triangle transversals using either vertices or edges. The computational
complexity of the decision versions associated to these problems is demonstrated for
the case of planar and maximal planar graphs. Regarding vertex-transversals, we
present four algorithms along with experimental results. We also prove two theo-
rems on the complexity of the guarding terrains problem. At last, we describe the
interface of our data structure and its application for constructing Delaunay trian-
gulations of planar point sets. Our results show that, on the average, it is possible
to reduce in 12% the number of stored references, while maintaining its performance
similar to the one of a standard vertex-based structure.
viii
Sumario
Lista de Figuras xi
Lista de Tabelas xiv
1 Introducao 1
1.1 Motivacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Organizacao e resumo da tese . . . . . . . . . . . . . . . . . . . . . . 3
2 Preliminares 6
2.1 Elementos de Teoria dos Grafos . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Coloracoes Policromaticas . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Emparelhamento Maximal, Maximo e Perfeito . . . . . . . . . 10
2.2 Satisfabilidade e suas variacoes . . . . . . . . . . . . . . . . . . . . . 11
2.3 Conjunto Transversal de Triangulo . . . . . . . . . . . . . . . . . . . 13
2.4 Vigilancia em Terrenos . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Classes de Estruturas de Dados . . . . . . . . . . . . . . . . . . . . . 17
2.6 Estruturas de dados para triangulacoes . . . . . . . . . . . . . . . . . 18
2.6.1 Estruturas Baseadas em Face . . . . . . . . . . . . . . . . . . 19
2.6.2 Estruturas Baseadas em Aresta . . . . . . . . . . . . . . . . . 21
2.6.3 Estruturas Baseadas em Vertice . . . . . . . . . . . . . . . . . 22
3 Transversal por Vertice 25
3.1 Complexidade de Transversais por Vertice . . . . . . . . . . . . . . . 25
ix
3.2 Vigilancia de Terrenos com Guardas-Vertice . . . . . . . . . . . . . . 29
3.3 Algoritmos para Transversais por Vertice . . . . . . . . . . . . . . . . 31
3.3.1 Algoritmo Otimo no Pior Caso . . . . . . . . . . . . . . . . . 32
3.3.2 Algoritmo Guloso . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.3 Algoritmos Randomizados . . . . . . . . . . . . . . . . . . . . 34
3.3.4 Uma 3-aproximacao . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Resultados Experimentais . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Transversal por Aresta 46
4.1 Complexidade de transversais por aresta . . . . . . . . . . . . . . . . 48
4.2 Vigilancia de Terrenos por Guardas-aresta . . . . . . . . . . . . . . . 52
5 Representacao de triangulacoes bidimensionais 54
5.1 A Estrutura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.1.1 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2 Construcao da Triangulacao de Delaunay . . . . . . . . . . . . . . . . 59
5.3 Resultados Experimentais . . . . . . . . . . . . . . . . . . . . . . . . 61
6 Consideracoes Finais 69
Referencias Bibliograficas 71
x
Lista de Figuras
2.1 Polıgono simples no formato de “pente” com 15 vertices. Sao ne-
cessarios 5 guardas (pontos pretos em destaque) para vigiar todo o
seu interior, onde cada guarda e responsavel por um “dente” do “pente”. 15
2.2 Grafo subjacente a um terreno convexo com 7 vertices que precisa de
ao menos 3 guardas para ser vigiado. Um exemplo de conjunto de
guardas mınimo esta indicado pelos vertices preenchidos na cor preta. 16
3.1 Subgrafo Gi correspondente a variavel xi. . . . . . . . . . . . . . . . . 27
3.2 Exemplo de grafo construıdo pela reducao apresentada no Teo-
rema 3.1 para uma instancia de 3-Sat2+1 Planar dada por (x1 ∨x2 ∨ x4) ∧ (x1 ∨ x3 ∨ x4) ∧ (x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x2 ∨ x3). . . . . . . . 28
3.3 Subdivisao de uma face hexagonal segundo a reducao apresentada no
Teorema 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 (a) Subdivisao e (b) secao transversal de uma face hexagonal apos a
reducao apresentada no Teorema 3.3. . . . . . . . . . . . . . . . . . . 31
3.5 Ilustracao das distribuicoes de pontos no plano utilizadas para avaliar
os algoritmos de transversais de triangulos por vertice. . . . . . . . . 38
3.6 (a) Tempo de CPU gasto por cada algoritmo para determinar trans-
versais de triangulos e sua (b) razao de vertices selecionados para tri-
angulacoes de pontos distribuıdos uniformemente no interior de um
quadrado unitario. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
xi
3.7 (a) Tempo de CPU gasto por cada algoritmo para determinar trans-
versais de triangulos e sua (b) razao de vertices selecionados para tri-
angulacoes de pontos distribuıdos uniformemente no interior de um
cırculo unitario. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.8 (a) Tempo de CPU gasto por cada algoritmo para determinar trans-
versais de triangulos e sua (b) razao de vertices selecionados para
triangulacoes de pontos normalmente distribuıdos no interior de um
quadrado unitario. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.9 (a) Tempo de CPU gasto por cada algoritmo para determinar trans-
versais de triangulos e sua (b) razao de vertices selecionados para
triangulacoes de pontos distribuıdos segundo a distribuicao normal
ponderada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1 (a) Exemplo de grafo planar G e (b) um transversal de triangulos
por aresta de G de tamanho 2. As arestas mais espessas desenhadas
em vermelho e azul pertencem ao transversal. As regioes hachuradas
representam as faces cobertas por cada uma destas arestas. . . . . . . 47
4.2 (a) Subgrafo Gi associado com a variavel xi. (b) Esquema do grafo
associado resultante a formula de 3-Sat2+1 Planar (x1 ∨ x2 ∨ x4) ∧(x1 ∨ x3 ∨ x4) ∧ (x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x2 ∨ x3). . . . . . . . . . . . . . 49
4.3 Exemplos de construcoes de triangulacoes para faces consistindo de
(a) 4 vertices e (b) 5 vertices. As areas hachuradas indicam os unicos
triangulos cobertos por arestas com extremidades no ciclo mais externo. 52
5.1 Esquema de representacao de uma triangulacao com 9 vertices, in-
cluindo o vertice infinito, utilizando a estrutura de dados baseada em
transversais de triangulos. Vertices guardas e guardados sao indica-
dos por cırculos e quadrados, respectivamente. . . . . . . . . . . . . . 56
xii
5.2 Ilustracao das triangulacoes calculadas pela implementacao da estru-
tura proposta para quatro tipos diferentes de distribuicoes de pontos
no plano. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3 (a) Tempo de CPU gasto por cada implementacao na construcao de
triangulacoes de Delaunay e (b) numero de referencias representadas
para o conjunto de pontos distribuıdos uniformemente no interior de
um quadrado unitario. . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4 (a) Tempo de CPU gasto por cada implementacao na construcao de
triangulacoes de Delaunay e (b) numero de referencias representadas
para o conjunto de pontos distribuıdos uniformemente no interior de
um cırculo unitario. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.5 (a) Tempo de CPU gasto por cada implementacao na construcao de
triangulacoes de Delaunay e (b) numero de referencias representadas
para o conjunto de pontos normalmente distribuıdos no interior de
um quadrado unitario. . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.6 (a) Tempo de CPU gasto por cada implementacao na construcao de
triangulacoes de Delaunay e (b) numero de referencias representadas
para o conjunto de pontos distribuıdos segundo a distribuicao normal
ponderada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
xiii
Lista de Tabelas
2.1 Numero de referencias utilizadas e custo de acesso a informacoes de
adjacencias em estruturas de dados para a representacao de trian-
gulacoes 2D. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1 Tempos de CPU em segundos gasto por cada etapa do algoritmo de
2-coloracao policromatica e razao entre o tamanho de um transversal
X e o numero de vertices da triangulacao de diferentes distribuicoes
de pontos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
xiv
Capıtulo 1
Introducao
Uma triangulacao e um tipo de decomposicao espacial bastante utilizada para repre-
sentar formas geometricas complexas. Esta descreve desde domınios de definicao de
equacoes diferenciais a personagens de filmes de animacao por computador. Devido
a sua flexibilidade, triangulacoes sao normalmente preferidas as malhas poligonais
arbitrarias. Implementacoes atuais de metodos de renderizacao, tais como ray tra-
cing e radiosidade, dao muitas vezes preferencia a triangulacoes devido ao melhor
desempenho alcancado com esta classe de decomposicao.
A representacao computacional de triangulacoes e geralmente dividida em duas
partes: geometria e topologia (ou combinatoria ou conectividade). Os vertices, as
arestas e as faces, bem como suas relacoes de incidencia e adjacencia, pertencem a
parte topologica. A geometria compreende as coordenadas dos vertices.
Muitas vezes, as triangulacoes representam a maior parte da memoria consumida
por uma aplicacao. Nestes casos, o tempo gasto em consultas sobre a triangulacao
propriamente dita torna-se preponderante no custo final da implementacao. Isto tem
sido agravado pelo fato de que a capacidade de armazenamento e aquisicao de dados
avanca mais rapidamente do que a velocidade de processamento dos computadores.
Em arquiteturas baseadas na utilizacao de memorias cache, e primordial reduzir
o numero de acessos a memoria RAM, mantendo os dados manipulados o maior
tempo possıvel dentro dos caches, pois o custo de acesso a RAM e sempre superior
ao custo de acesso a qualquer nıvel de cache. Portanto, quanto menor o volume
1
de dados processado, menor sera a quantidade de acessos a RAM. Sendo assim,
torna-se imprescindıvel desenvolver estruturas de dados cada vez mais eficientes
em termos de espaco. Esta eficiencia tambem deve levar em conta o tempo gasto
em consultas. O problema e que uma reducao no tamanho da representacao vem
geralmente acompanhada de um aumento no custo de sua manipulacao.
Neste sentido, diversos trabalhos tem sido realizados com o intuito de desenvolver
representacoes de triangulacoes mais compactas [1–20]. Ha basicamente dois tipos
de finalidades para a compressao: tratamento em memoria RAM e tratamento em
memoria auxiliar (discos rıgidos, memorias flash, fitas magneticas, etc). Alem disso,
pode-se optar por comprimir os dados geometricos e/ou topologicos.
O foco desta tese esta em metodos de compressao da topologia para manipulacao
em memoria RAM de triangulacoes bidimensionais. Apresentamos uma estrutura
de dados baseada em vertices, a qual emprega o conceito de conjuntos transversais
de triangulos por vertice para a reducao da redundancia no armazenamento da
conectividade. O estudo de conjuntos transversais nos levou ainda a demonstracao
de alguns resultados teoricos sobre a complexidade de problemas de vigilancia em
terrenos associados.
1.1 Motivacao
Recentemente, foi desenvolvida uma estrutura de dados que permitiu a construcao
de uma triangulacao consistindo de 110 milhoes de triangulos, consumindo 4,58 bytes
por face [1]. Apesar da elevada eficiencia desta estrutura, os esforcos dos autores
ficaram concentrados na compressao do tamanho das referencias utilizadas, sem dar
atencao a estrutura combinatoria em si. Como cada vertice armazena referencias
a todos os seus vizinhos, cada aresta e representada quatro vezes, pois existem
duas faces adjacentes a cada aresta. As faces sao implicitamente armazenadas tres
vezes cada, uma devido a cada um de seus vertices. Neste contexto, observamos
que poderıamos aplicar conceitos de conjuntos transversais de triangulos de modo a
aperfeicoar a representacao das informacoes topologicas.
2
1.2 Objetivo
Esta tese tem por objetivo o desenvolvimento de uma estrutura de dados capaz de
representar triangulacoes bidimensionais, reduzindo o espaco em memoria consu-
mido pela informacao de conectividade. Deseja-se que este ganho em memoria nao
implique em uma reducao acentuada na velocidade de acesso aos dados topologicos.
1.3 Organizacao e resumo da tese
O Capıtulo 2 apresenta definicoes e resultados empregados ao longo dos capıtulos
seguintes. Serao abordados, de modo breve, alguns conceitos de teoria dos gra-
fos, logica, complexidade, geometria computacional e teoria da informacao que per-
meiam esta tese. Daremos a definicao do problema de satisfabilidade e algumas de
suas principais variacoes, as quais sao bastante uteis para demonstrar resultados
de complexidade. Introduziremos a definicao de conjuntos transversais, tanto em
sua forma mais geral, quanto para o caso restrito a faces triangulares, e apresen-
taremos resultados encontrados na literatura que nos auxiliaram a desenvolver o
restante deste trabalho. Uma ligeira descricao do problema de vigilancia em terre-
nos sera suficiente para deixar clara sua relacao com conjuntos transversais. Tudo
isto contribuira tambem para estabelecer a terminologia adotada.
O problema de determinar um transversal de triangulos por vertice mınimo para
grafos planares e a essencia do Capıtulo 3. Dois teoremas caracterizando sua com-
plexidade serao apresentados. O primeiro considerando grafos planares arbitrarios
e, o segundo, grafos maximais planares ou triangulacoes. Sera demonstrado que e
NP-completo decidir se um grafo G possui um transversal de triangulos de tama-
nho no maximo k ≥ 0 para qualquer uma destas classes de grafos. Alem disso, se
G for um grafo planar arbitrario, veremos que a NP-dificuldade e mantida mesmo
quando o grau maximo for igual a 5. Estes resultados possibilitarao demonstrar que
o problema de posicionar guardas nos vertices de um terreno poliedrico e tao difıcil
quanto o de calcular um transversal de triangulos do grafo associado a este terreno.
3
Nossa reducao construira um terreno com O(n) faces, ao contrario da construcao
quadratica de COLE e SHARIR [21]. Apresentamos ainda a avaliacao experimen-
tal de quatro algoritmos para calcular transversais de triangulos por vertice: uma
solucao otima no pior caso [22], um guloso, dois algoritmos com escolha aleatoria e
uma 3-aproximacao.
No Capıtulo 4, nos concentraremos em uma variante de transversais denominada
transversais por aresta. O conceito de (F,H)-transversais sera introduzido com o
objetivo de levar-nos a definicao de transversais por aresta. Assim como para o caso
de transversais por vertice, estudaremos a complexidade de problemas associados,
tais como a determinacao de transversais por aresta mınimos e o problema de po-
sicionamento de guardas-aresta em terrenos. No caso de transversais por aresta de
grafos planares, observaremos que mesmo ao reduzir de 7 (devido a BRUGMANN
et al. [23]) para 5 o grau maximo do grafo de entrada, a NP-dificuldade do problema
de decisao associado permanece a mesma. Mais uma vez, nossa reducao para o pro-
blema de guardas-aresta produzira terrenos com um numero linear de faces, o que
representa uma melhoraria em comparacao a construcao de tamanho O(mn) devido
a ZHU [24].
A estrutura de dados proposta para representar triangulacoes bidimensionais sera
apresentada no Capıtulo 5. Descreveremos sua interface e aplicacao em uma imple-
mentacao de um algoritmo de construcao incremental randomizada de triangulacoes
de Delaunay 2D. Seu desempenho, em termos do numero de referencias e tempo de
CPU, sera comparado com o de uma implementacao propria sem compressao da es-
trutura utilizada como base de partida [1] e com o de uma implementacao fornecida
por uma biblioteca de algoritmos geometricos bastante difundida [25]. Mostraremos
como a ideia de conjunto transversal de triangulos pode ser utilizada para reduzir de
6n (valor utilizado pelo esquema de BLANDFORD et al. [1]) para 5n o numero total
de referencias armazenadas. Demonstraremos experimentalmente que esta reducao
implicara em uma implementacao cerca de 18% mais veloz do que o esquema des-
comprimido de BLANDFORD et al. [1].
4
Por fim, o Capıtulo 6 contem conclusoes gerais e referencias a caminhos inexplo-
rados, sugerindo direcoes para pesquisas futuras.
No momento da defesa desta tese, os resultados apresentados no Capıtulo 4
fazem parte dos anais do 25◦ European Workshop of Computational Geometry [26].
Estes resultados foram agrupados com os do Capıtulo 3 para a composicao de um
artigo expandido sobre conjuntos transversais em grafos (maximais) planares, a ser
submetido. Tambem encontra-se em preparacao um artigo referente ao conteudo do
Capıtulo 5.
5
Capıtulo 2
Preliminares
Os fundamentos envolvidos nesta tese pertencem a uma intersecao entre diferentes
areas da engenharia e computacao. Sao abrangidos conceitos de teoria dos grafos,
logica, complexidade, geometria computacional e teoria da informacao. Apresen-
tamos, neste capıtulo, as principais definicoes e teoremas tomados emprestados de
cada uma destas areas, necessarios a obtencao dos resultados contidos nos proximos
capıtulos. Isto servira tambem para estabelecer a notacao adotada.
2.1 Elementos de Teoria dos Grafos
Um grafo G e um par ordenado de conjuntos disjuntos (V (G), E(G)), onde E(G) e
composto por pares nao ordenados de elementos de V (G). Os elementos de V (G)
sao denominados vertices do grafo G, e os elementos de E(G) sao as arestas de G.
Quando nao houver duvidas quanto ao grafo subjacente, escreveremos somente V
e E para denotar os conjuntos de vertices e arestas de G. A menos que seja dito
o contrario, usaremos n e m para denotar a cardinalidade dos conjuntos V e E,
respectivamente.
Um laco e uma aresta cujas extremidades sao identicas. Uma multiaresta e um
conjunto de ao menos duas arestas com extremidades identicas. Um grafo e dito
simples se este nao contem nem lacos nem multiarestas. Caso contrario, este e dito
ser um multigrafo.
6
Nesta tese, nos ocuparemos apenas com grafos simples cujo conjunto de vertices
e finito, o que implica na finitude de E, o qual possui no maximo(
n2
)arestas.
Dados dois vertices u, v ∈ V , diz-se que u e adjacente ou vizinho a v se a aresta
(u, v) pertence a E. Se uma aresta e ∈ E contem como extremidade um vertice v,
entao e e incidente em v. A vizinhanca N(u) de um vertice u e igual ao conjunto de
seus vertices incidentes. O grau de um vertice u e igual ao numero de vertices em sua
vizinhanca. Um vertice cujo grau e igual a zero e denominado isolado. Um grafo e
regular quando todos os seus vertices possuem o mesmo grau. Se um grafo e regular
e o grau de seus vertices for igual a k, este e denominado k-regular. Denota-se por
δ(G) e ∆(G) os graus mınimo e maximo em G, respectivamente.
Um grafo e dito completo se for simples e seus vertices forem dois-a-dois adja-
centes. O grafo completo de n vertices e denotado por Kn. Logo, K2 e uma aresta
e K3 e um triangulo.
Um grafo e bipartido se for possıvel agrupar seus vertices em dois conjuntos de
vertices V1 e V2 tal que cada vertice nao possui vizinhos no conjunto no qual ele
proprio esta contido. Se G for tambem completo, entao G e um grafo bipartido
completo, denotado por Ki,j, onde i = |V1| e j = |V2|.Dados dois grafos G e G′, se V (G′) ⊆ V (G) e E(G′) ⊆ E(G), entao G′ e um
subgrafo de G. Se G′ 6= G, entao G′ e um subgrafo proprio de G. O subgrafo induzido
G[X] de um conjunto X ⊆ V (G) e um par composto por X e o conjunto de todas
as arestas de G entre vertices de X. O subgrafo induzido por um grafo G′ ⊆ G e
igual ao subgrafo induzido pelo conjunto V (G′).
Um caminho em um grafo G e um subgrafo simples cujos vertices podem ser
organizados em uma sequencia linear de tal modo que dois vertices sao adjacentes
em G somente se estes forem consecutivos nesta sequencia, caso contrario estes
devem ser nao adjacentes um ao outro. Os ciclos sao caminhos onde os vertices
podem ser distribuıdos em uma sequencia circular. O tamanho de um caminho ou
ciclo e igual ao seu numero de arestas. Denota-se um caminho (resp., um ciclo) com
n vertices por Pn (resp., Cn). Se G nao possui ciclos, entao G e acıclico.
7
Um grafo G e conexo se quaisquer dois de seus vertices estiverem ligados por um
caminho. Caso contrario, G e desconexo. Se e ∈ E for uma aresta de G tal que o
grafo G − {e} e desconexo, dizemos que e e uma ponte ou uma aresta de corte de
G. Grafos conexos acıclicos sao denominados de arvores.
Dados dois grafos G1 e G2, se existir uma bijecao entre os conjuntos V (G1) e
V (G2), e estes possuırem o mesmo numero de arestas, entao G1 e G2 sao isomorfos.
Um grafo e dito planar se este pode ser desenhado no plano sem a existencia de
cruzamentos entre arestas. As regioes conexas do plano delimitadas por um desenho
de um grafo planar G sao as faces de G. O conjunto de todas as faces de um grafo
G e denotado por F (G) ou F , abreviadamente, desde que esteja claro seu grafo de
definicao. A face mais externa de um grafo e denominada ilimitada ou infinita. Um
grafo maximal planar e aquele ao qual a adicao de apenas uma aresta levara ao
aparecimento de arestas cruzadas.
Diz-se que um grafo planar G′ e um refinamento de um grafo G se o conjunto
de arestas de G estiver contido no conjunto de arestas de G′. Observe que um grafo
maximal planar nao pode ser refinado a menos da criacao de vertices.
Em geometria computacional, uma triangulacao e definida como uma decom-
posicao em triangulos do fecho convexo de um conjunto de pontos. Ja em teoria
dos grafos, o termo triangulacao e utilizado como sinonimo para grafos maximais
planares. De modo a uniformizar o tratamento deste conceito, assumiremos que
nossas triangulacoes estarao sempre equipadas com um vertice fictıcio no infinito,
conectado a todos os vertices pertencentes ao fecho convexo do conjunto de pontos
subjacente. Isto torna a triangulacao homeomorfa a triangulacao da esfera S3 ⊂ R3.
Deste modo, e facil ver que uma triangulacao de n pontos possuira 3n− 6 arestas e
2n− 4 faces, o que tambem vale para grafos maximais planares.
Uma k-coloracao dos vertices de um grafo G e uma funcao f : V → S, onde S
e um conjunto de k cores. Uma coloracao e dita propria se quaisquer dois vertices
adjacentes em G possuırem cores distintas. O numero cromatico χ(G) de um grafo G
e o menor inteiro positivo k tal que exista uma k-coloracao propria de seus vertices.
8
Se um grafo pode ser colorido com k cores, dizemos que ele e k-colorıvel.
Em teoria dos grafos extremal, uma questao bastante estudada e a de obter
limites superiores para o numero de cores necessarias para colorir propriamente di-
ferentes classes de grafos. E facil ver que qualquer grafo pode ser colorido utilizando
∆(G)+1 cores. Entretanto, sabe-se que o calculo do numero cromatico de um grafo,
mesmo sendo este planar, e um problema intratavel computacionalmente.
Teorema 2.1 ([27, 28]). O problema de decidir se um grafo pode ser 3-colorido e
NP-completo, mesmo se o grafo for planar e possuir grau maximo 4.
Para grafos maximais planares, a existencia de uma 3-coloracao dos vertices foi
caracterizada ainda no seculo 19, empregando o conceito de grafos Eulerianos (grafos
onde o grau de qualquer um de seus vertices e par). Com isto, pode-se verificar em
tempo O(n) se uma triangulacao possui uma 3-coloracao propria.
Teorema 2.2 ([29–31]). Uma grafo maximal planar G possui uma 3-coloracao
propria de seus vertices se e somente se G for Euleriano.
No ano de 1977, APPEL et al. [32] apresentaram uma demonstracao auxiliada
por computador que confirmava uma conjectura de que grafos planares sempre po-
dem ser coloridos utilizando ate quatro cores.
Teorema 2.3 (Teorema das Quatro Cores [32]). Todo grafo planar sem lacos e
4-colorıvel.
Este mesmo teorema foi demonstrado mais tarde por ROBERTSON et al. [33],
ainda com o auxılio de um computador, mas reduzindo o tempo total de verificacao.
2.1.1 Coloracoes Policromaticas
Dada uma k-coloracao de um grafo planar G, diz-se que uma face f ∈ F (G) e po-
licromatica se todas as k cores forem utilizadas para colorir os vertices de f . Uma
k-coloracao de um grafo G e denominada de k-coloracao com faces policromaticas,
9
ou simplesmente de coloracao policromatica, se todas as faces de G forem poli-
cromaticas. O numero policromatico p(G) de um grafo G e o maior inteiro positivo
k tal que G admita uma k-coloracao policromatica.
Seja g(G) o tamanho da menor face em um grafo planar G. Fica claro que
p(G) ≤ g(G). Alem disso, p(G) ≥ 2 para todo grafo planar G com g(G) ≥ 3, pois
se p(G) for igual a 1, surgirao faces monocromaticas em G, o que e proibido.
A existencia de ao menos uma 2-coloracao policromatica de um grafo planar
arbitrario e garantida por intermedio do emprego do Teorema das Quatro Cores
[34]. Com efeito, seja G um grafo planar munido de uma 4-coloracao. Seja S =
{V1, V2, V3, V4}, onde |V1| ≤ |V2| ≤ |V3| ≤ |V4|, o particionamento de seu conjunto de
vertices induzido por esta coloracao. Defina um novo particionamento S ′ = {V ′1 , V ′2},onde V ′1 = V1∪V2 e V ′2 = V3∪V4. Observe que, deste modo, nao existirao triangulos
monocromaticos em G. Logo, S ′ e uma 2-coloracao policromatica de G.
Posteriormente, BOSE et al. [22] apresentaram uma demonstracao alternativa
sem empregar o Teorema das Quatro Cores, a qual fornece um algoritmo linear para
o calculo de 2-coloracoes policromaticas.
Dada uma triangulacao arbitraria G, temos que 2 ≤ p(G) ≤ 3. Foi estudando
esta desigualdade para grafos planares quaisquer que ALON et al. [35] obtiveram o
resultado mais geral a seguir.
Teorema 2.4 ([35]). Se G e um grafo planar com g(G) ≥ 3, entao vale o seguinte:
⌊3g − 5
4
⌋≤ p(G) ≤
⌊3g + 1
4
⌋. (2.1)
2.1.2 Emparelhamento Maximal, Maximo e Perfeito
Um emparelhamento M de um grafo G e uma colecao de arestas de G dois-a-dois dis-
juntas. Diz-se que um vertice v esta saturado por um emparelhamento M , se existir
uma aresta e ∈ M que incide em v. Um emparelhamento e dito maximo se, dado
qualquer outro emparelhamento M ′, valer a desigualdade |M | ≥ |M ′|. Se o tamanho
de um emparelhamento M nao puder ser aumentado com a insercao de mais uma
10
aresta, entao M e maximal. Um emparelhamento perfeito de um grafo e qualquer
emparelhamento que sature todos os seus vertices. A existencia de emparelhamen-
tos perfeitos em grafos 3-regulares biconexos foi caracterizada por PETERSEN [36],
ao demonstrar que se existir um grafo 3-regular sem um emparelhamento perfeito,
entao este dever conter ao menos tres pontes.
Teorema 2.5 ([36, 37]). Todo grafo 3-regular biconexo possui um emparelhamento
perfeito.
O primeiro algoritmo polinomial para determinar emparelhamentos maximos
em grafos arbitrarios foi desenvolvido por EDMONDS [38], cuja complexidade e
O(n4). Quinze anos depois, MICALI e VAZIRANI [39] obtiveram um algoritmo
consideravelmente mais rapido, de tempo O(m√n). Posteriormente, surgiram dois
outros algoritmos com esta mesma complexidade [40, 41]. No caso particular de
grafos 3-regulares biconexos, um algoritmo de BIEDL et al. [42] e capaz de calcular
emparelhamentos maximos em tempo O(n log4 n). Se alem de 3-regular, o grafo for
planar, BIEDL et al. [42] tambem demonstrou como obter uma solucao em O(n)
passos.
2.2 Satisfabilidade e suas variacoes
Seja X = {x1, x2, . . . , xn} um conjunto de variaveis Booleanas. A cada variavel xi,
associa-se os literais xi e xi. O literal xi assume valor verdadeiro se e somente se xi
for igual a falso, e vice-versa. Por convencao, assuma que 1 corresponde a verdadeiro
e 0 corresponde a falso. Uma atribuicao de verdade e uma aplicacao de X em {0, 1}.Uma clausula em X e definida como uma disjuncao de literais associados a um
subconjunto de X. Diz-se que uma clausula e satisfatıvel se existe uma atribuicao
de verdade tal que ao menos um de seus literais assume valor verdadeiro. Uma
expressao Booleana ϕ esta na forma normal conjuntiva (FNC) se esta puder ser
escrita como∧m
j=1Cj, onde Cj e uma clausula em X. Portanto, uma expressao ϕ na
FNC e satisfatıvel se todas as suas clausulas sao satisfeitas simultaneamente. Um
11
problema bastante conhecido envolvendo este tipo de expressoes e o seguinte:
Satisfabilidade (Sat)
Entrada: Expressao Booleana ϕ na forma normal conjuntiva.
Questao: A expressao ϕ e satisfatıvel?
O problema Sat e conhecido como o primeiro problema comprovadamente NP-
completo [43]. Sua estrutura simples contribuiu para sua popularizacao nas provas
por construcao de reducoes polinomiais.
Ao buscar caracterizar a fronteira entre P e NP, e comum estudar restricoes de
um problema mais geral. No caso do Sat, pode-se restringir o tamanho das clausulas,
o numero de ocorrencias das variaveis, etc. Por exemplo, COOK [43] observou que o
Sat quando restrito a clausulas de tamanho exatamente 3 permanece NP-completo.
Este problema e mais conhecido como 3-Sat.
Dada uma expressao ϕ na FNC, o seu grafo de incidencia e um grafo bipartido
G[ϕ] := (V,E) com biparticao (Vc, Vv), onde os conjuntos Vc e Vv representam
as variaveis e as clausulas de ϕ, respectivamente. As arestas de G[ϕ] denotam a
relacao de inclusao entre variaveis e clausulas. E surpreendente saber que o 3-Sat
permanece difıcil de resolver ainda que o grafo de suas formulas sejam planares. Isto
foi demonstrado por LICHTENSTEIN [44], resultando no seguinte teorema:
Teorema 2.6 ([44]). O problema 3-Sat Planar e NP-completo.
Seja (k, s)-FNC o conjunto de expressoes Booleanas na forma normal conjuntiva
com clausulas contendo exatamente k literais distintos, os quais ocorrem em ate
s clausulas. Define-se entao o problema (k, s)-Sat como o de decidir se uma dada
expressao (k, s)-FNC e satisfatıvel. TOVEY [45] foi o primeiro a estudar este tipo de
questao. Ele observou que o problema (3, 3)-Sat e trivialmente satisfatıvel, ao passo
que o problema (3, 4)-Sat ja se torna NP-completo. Para demonstrar a trivialidade
do (3, 3)-Sat, Tovey construiu um grafo de incidencia de uma expressao (3, 3)-FNC
e percebeu o seguinte. Se S e um subconjunto de Vc, entao |N(S)| e maior ou igual
ao tamanho de S. Logo, pelo Teorema de HALL [46], existe um emparelhamento
que satura Vc. Para construir uma atribuicao de verdade que satisfaca ϕ, basta
12
associar o valor verdadeiro ao literal correspondente a variavel saturada por este
emparelhamento. Desde que existem algoritmos para determinar emparelhamentos
em grafos bipartidos em tempo linear, o problema (3, 3)-Sat pertence a P.
Considere agora mais uma variacao de problemas de satisfabilidade, o 3-Sat2+1,
onde as clausulas possuem 2 ou 3 literais e as variaveis ocorrem exatamente 3 vezes
(duas positivamente e uma negativamente, ou ao contrario). A seguinte afirmacao
e verdadeira [45]:
Teorema 2.7 ([45]). O problema 3-Sat2+1 e NP-completo.
Com base nos Teoremas 2.6 e 2.7, podemos assumir o seguinte:
Lema 2.1. O problema 3-Sat2+1 Planar e NP-completo.
2.3 Conjunto Transversal de Triangulo
Seja G um grafo arbitrario e H uma famılia de grafos. Um H-subgrafo de G e um
subgrafo induzido de G isomorfo a um elemento de H. Um conjunto X ⊆ V (G) e
um H-transversal de G se todos os H-subgrafos de G forem interceptados por X.
Um transversal X ∈ V e dito independente se ∆(G[X]) = 0. Um emparelhamento
transversal e todo transversal onde ∆(G[X]) ≤ 1. O numero transversal τ(G) de
um grafo G e a cardinalidade mınima de um transversal de G.
O problema de decidir se existe um H-transversal em um grafo G e formulado
da seguinte maneira:
H-Transversal
Entrada: Grafo G, famılia de grafos H e inteiro positivo k.
Questao: Existe um H-transversal de G de tamanho no maximo k?
Em resposta a esta questao, YANNAKAKIS [47] demonstrou o teorema a seguir:
Teorema 2.8 ([47]). H-Transversal e NP-completo.
Considerando uma famılia de grafos H particular, o problema H-Transversal
pode recair em um problema bastante conhecido. Por exemplo, fazendo H = {K2},
13
um H-transversal e equivalente ao Cobertura de Vertices [48]. Quando H =
{K3}, chegamos a formulacao do principal problema estudado nesta tese.
Transversal de Triangulos por Vertice
Entrada: Grafo G e inteiro positivo k.
Questao: Existe um transversal de triangulos por vertice de G com tamanho no
maximo k?
Recentemente, GROSHAUS et al. [49] estudaram transversais de ciclos em grafos
arbitrarios. Eles tambem consideraram transversais de triangulos em grafos com
grau maximo limitado.
Teorema 2.9 ([49]). Transversal de Triangulos por Vertice e NP-completo
para grafos com grau maximo igual a 4.
Em termos de algoritmos para calcular um transversal de triangulos em grafos
arbitrarios, GROSHAUS et al. [49] desenvolveram um algoritmo 3-aproximativo.
2.4 Vigilancia em Terrenos
Desde sua formulacao por Victor Klee na decada de 70, o problema da galeria de
arte tem estimulado um numero crescente de pesquisadores, notavelmente do campo
da geometria computacional. A questao original pergunta pelo numero mınimo de
guardas que podem vigiar o interior de uma galeria. Na sua versao padrao, uma gale-
ria e representada por um polıgono simples e os guardas sao posicionados em pontos
fixos pertencentes a este polıgono. CHVATAL [50] foi o primeiro a demonstrar que
bn/3c guardas sao sempre suficientes e algumas vezes necessarios. Utilizando o fato
de que a triangulacao de um polıgono simples e 3-colorıvel, FISK [51] desenvolveu
uma demonstracao mais simples e elegante para o mesmo problema. A Figura 2.1
contem um exemplo de um polıgono simples que requer no mınimo bn/3c guardas.
Varias particularizacoes tambem tem sido estudadas, tais como considerar
polıgonos com buracos e polıgonos ortogonais, ou permitir que os guardas patru-
lhem ao longo de areas de formas das mais variadas. As referencias [52–54] sao
14
Figura 2.1: Polıgono simples no formato de “pente” com 15 vertices. Sao necessarios
5 guardas (pontos pretos em destaque) para vigiar todo o seu interior, onde cada
guarda e responsavel por um “dente” do “pente”.
excelentes coletaneas de resultados sobre este tema. Um caso especial que sera
abordado nesta tese e o seguinte.
Vigilancia de Terreno
Entrada: Terreno poliedrico T e inteiro positivo k.
Questao: E possıvel vigiar o terreno T utilizando no maximo k guardas?
Um terreno poliedrico T pode ser visto como o grafico de uma funcao linear por
partes z = F (x, y), definida sobre o plano xy [21]. Dados dois pontos u e v em T ,
dizemos que u e visıvel a partir de v se o segmento de reta uv nao intercepta T em
nenhum ponto estritamente abaixo da superfıcie do terreno. A regiao de visibilidade
de um ponto u e definida pelo conjunto de pontos em T visıveis a partir de u.
Quando os guardas sao postos em qualquer ponto sobre o terreno, devendo per-
manecer parados no mesmo local durante todo o seu expediente, eles sao denomina-
dos guardas-ponto. Se restringirmos ainda mais os lugares disponıveis para o posici-
onamento dos guardas como sendo estritamente os vertices do grafo subjacente ao
terreno, este tipo de guarda e denominado guarda-vertice. Em outro modelo bastante
conhecido de guarda, o guarda-aresta, ele pode patrulhar ao longo das arestas do
terreno. Estes diferentes tipos de guardas dao origem aos problemas de Vigilancia
de Terreno com Guardas-Ponto, Guardas-Vertice e Guardas-Aresta.
Segundo BOSE et al. [22, 55], para vigiar um terreno com n vertices e necessario e
as vezes suficiente utilizar bn/2c guardas-vertice. Este resultado foi demonstrado por
15
Figura 2.2: Grafo subjacente a um terreno convexo com 7 vertices que precisa de
ao menos 3 guardas para ser vigiado. Um exemplo de conjunto de guardas mınimo
esta indicado pelos vertices preenchidos na cor preta.
meio de uma construcao recursiva de uma famılia de terrenos convexos que apenas
sao cobertos se exatamente bn/2c vertices forem selecionados. O grafo subjacente
ao terreno utilizado como caso base da recursao esta ilustrado na Figura 2.2.
Quando se trata de guardas-aresta, o numero de guardas e obviamente inferior.
EVERETT e RIVERA-CAMPO [56] demonstraram que bn/3c guardas-aresta sao
suficientes para cobrir um terreno poliedrico. O melhor limite inferior de que temos
conhecimento e de b(4n− 4)/13c guardas-aresta, devido a BOSE et al. [55].
As demonstracoes destes limites sobre o numero de guardas foram obtidas, na
verdade, considerando-se a versao discreta do problema de vigilancia em terrenos.
Neste caso, restringe-se a regiao de visibilidade de um guarda as faces nele incidentes.
Realmente, na pior das hipoteses, isto pode acontecer. Basta considerarmos um
terreno convexo com faces planas. Se, alem de convexo, o grafo G subjacente a T
for maximal planar, determinar um conjunto de guardas de cardinalidade mınima
para T e equivalente a calcular um transversal de triangulos por vertice mınimo de
G. Desde que todo terreno pode ser vigiado por no maximo bn/2c guardas [22, 55],
isto tambem deve valer para transversais de triangulos em grafos maximais planares.
Corolario 2.1. Todo grafo maximal planar G possui um transversal de triangulos
por vertice de tamanho no maximo bn/2c.
16
2.5 Classes de Estruturas de Dados
Seja C uma classe de objetos abstratos. Fixado um parametro de tamanho n, su-
ponha que a classe C pode ser particionada em subclasses finitas Cn de objetos
parametrizados por n. A entropia ‖Cn‖ de Cn e igual a quantidade media de bits
necessaria para representar um objeto aleatorio de Cn. Seja p(x) = Pr[x], x ∈ Cn,
uma distribuicao de probabilidades em Cn. A entropia de Cn e dada por:
‖Cn‖ = −∑x∈Cn
p(x) log2 p(x).
Supondo todos os objetos equiprovaveis, tem-se que:
‖Cn‖ = log2 |Cn|.
Com base nisto, uma estrutura de dados pode ser classificada como implıcita, su-
cinta e compacta. Representacoes implıcitas sao aquelas que armazenam exatamente
o numero de bits retornado pela entropia. Uma estrutura de dados e considerada
sucinta se esta consome ‖Cn‖ + o(‖Cn‖) bits. As estruturas compactas sao aquelas
que utilizam O(‖Cn‖) bits. Caso uma estrutura de dados nao se encaixe em nenhuma
destas classes, ela e denominada explıcita.
Seja Tn a classe de triangulacoes com n+ 2 vertices homeomorfas a triangulacao
da esfera tridimensional S3. Diz-se que duas triangulacoes sao equivalentes se estas
forem isomorfas. Neste caso, sabe-se que:
Teorema 2.10 ([57]). O numero de triangulacoes enraizadas, planares e 3-conexas
com n+ 2 vertices e igual a:
|Tn| = 2(4n− 3)!
n!(3n− 1)!.
Aplicando-se a aproximacao de Stirling para o fatorial, conclui-se que ‖Tn‖ vale
aproximadamente 3,24n bits. Isto quer dizer que 3,24n bits e um limite inferior
para o maximo de compressao possıvel a ser obtido por uma estrutura de dados
17
para triangulacoes bidimensionais. Apesar de ser difıcil obter uma implementacao
pratica de uma estrutura ocupando tao pouco espaco, ja existe um esquema teorico
capaz de alcancar tal limite [3].
2.6 Estruturas de dados para triangulacoes
Do ponto de vista teorico, a geometria computacional avancou consideravelmente
nos ultimos 30 anos. Desde o aparecimento da tese de SHAMOS [58] em 1978, gran-
des descobertas foram realizadas e uma quantidade enorme de material bibliografico
foi produzida. Alguns dos problemas mais abordados nesta area sao: calculo do
fecho convexo de pontos, construcao de envelopes de arranjos de hiperplanos, de-
composicao de polıgonos, busca por regiao e construcao triangulacoes de Delaunay.
Este ultimo e bastante conhecido da comunidade de computacao cientıfica por sua
aplicacao em metodos de geracao de malhas. Isto e justificado pelas propriedades
intrınsecas a uma triangulacao de Delaunay, notavelmente, a de maximizar o menor
angulo dos triangulos para o caso planar.
Pode-se afirmar que houve um aumento significativo do numero de imple-
mentacoes de algoritmos geometricos, bons exemplos sao a Computational Geo-
metry Algorithms Library (CGAL) e a C++ Library of Efficient Data Types and
Algorithms (LEDA). Estas duas bibliotecas, juntas, contemplam grande parte dos
problemas classicos de geometria computacional. As representacoes computacionais
para os tipos de dados manipulados, contudo, nao foram exploradas o suficiente. Um
bom exemplo e a representacao de triangulacoes utilizada pela biblioteca CGAL. E
uma estrutura de dados classica, a qual representa explicitamente os vertices e as
faces da triangulacao. Cada vertice armazena uma referencia (ou apontador) a uma
face incidente qualquer, e cada face possui apontadores para suas tres faces vizinhas
por aresta. Isto e interessante do ponto de vista do custo de consultas. Em termos de
memoria, entretanto, boa parte dos dados sao gastos com informacoes redundantes.
Podemos agrupar as estruturas de dados existentes para representacao de tri-
angulacoes segundo o tipo basico adotado: vertice, aresta ou face. Estruturas de
18
dados baseadas em face sao bastante utilizadas na pratica, principalmente, devido a
facilidade de implementacao. As estruturas baseadas em arestas ja foram bastante
estudadas, mas devido seu custo elevado em termos de memoria, estas sao mais
aplicadas na representacao de modelos geometricos com faces de dimensao variavel
do que na representacao de simples triangulacoes. Aparentemente mais simples, a
implementacao de estruturas baseadas em vertices na verdade envolvem um maior
esforco na concepcao dos algoritmos de manipulacao. Somando-se a isto, esta o fato
de que o custo de acesso aos seus dados e normalmente funcao do grau do vertice
em consideracao, ao inves de tempo O(1) fornecido pela maior parte dos esquemas
baseados em aresta ou face.
2.6.1 Estruturas Baseadas em Face
Sopa de triangulos
Em R2, um triangulo e definido por seus tres vertices, onde cada vertice e dado por
um par de pontos no plano. Assim, uma colecao de triangulos pode ser representada
pela uniao disjunta das coordenadas de seus vertices. Com efeito, uma triangulacao
com n vertices requer (6n− 12)× log n bits. Note que aqui nenhuma informacao de
adjacencia e armazenada. Entao, testar se dois vertices u e v sao adjacentes implica
em encontrar ao menos um triangulo da triangulacao contendo a aresta (u, v). Este
algoritmo levaria O(n) passos de tempo.
CGAL
A biblioteca de geometria computacional CGAL contem uma implementacao de
uma representacao baseada em face. Cada vertice guarda uma referencia para uma
de suas faces incidentes. As faces contem, alem de ponteiros para os vertices que
as compoem, tres ponteiros para as faces adjacentes por aresta. As arestas sao
representadas implicitamente por pares compreendendo uma face e um inteiro in-
dicando o vertice oposto a aresta representada. O resultado disto e um total de
13n − 4 ≈ 13n referencias por triangulacao. Em contrapartida, garante-se acesso
19
em O(1) as informacoes de adjacencias de uma face.
Castelli et al
Conceito surgido em 1989 [59], as estruturas sucintas tem despertado a atencao da
comunidade cientıfica devido a sua otimalidade em espaco e o seu compromisso com
o tempo de acesso as informacoes armazenadas. A maioria das estruturas sucintas
propostas e baseada nas construcoes de JACOBSON [59] e MUNRO e RAMAN [60]
para a representacao de arvores binarias, parenteses balanceados e grafos planares.
A ideia basica e particionar o objeto de entrada em blocos, e em diferentes nıveis,
de modo a tornar o acesso e o espaco consumidos assintoticamente otimos. Com
base nisto, e aproveitando a existencia de uma bijecao entre triangulacoes e arvores
[61], ALEARDI et al. [3] desenvolveram um esquema de representacao sucinto que
atinge a entropia para triangulacoes da esfera, ou seja, 3,24 bits por vertice.
Muitos dos resultados de ALEARDI et al. [3] sao de cunho estritamente teorico,
como alertado pelos proprios autores. Recentemente, alguns deles foram avaliados na
pratica por MEBARKI [62]. Na verdade, foram implementadas tres representacoes.
A primeira consiste em empregar rotulos inteiros ao inves de ponteiros em cima da
estrutura padrao utilizada pela CGAL. Os outros dois esquemas avaliados foram
justamente os propostos por ALEARDI et al. [3]. Um deles particiona a trian-
gulacao em estruturas pequenas de tamanho fixo as quais juntas dao origem a um
catalogo. A triangulacao fica representada entao por uma lista de ponteiros para
este catalogo. Isto faz com que o numero de referencias multiplas de triangulos aos
vertices e entre triangulos seja reduzido. O segundo esquema implementado consi-
dera catalogos com tamanhos dependentes do numero de pontos da triangulacao.
Isto visa diminuir o custo global associado com o grafo das sub-triangulacoes. Em
suma, sao criadas O(log n) sub-triangulacoes. Logo, estas sub-triangulacoes podem
utilizar referencias de tamanho O(n/ log n). Apesar dos ganhos em memoria faze-
rem jus aos previstos por ALEARDI et al. [3], a velocidade de processamento nao
foi melhorada em conjuntos de pontos massivos.
20
2.6.2 Estruturas Baseadas em Aresta
As estruturas baseadas em arestas mais conhecidas sao sem duvida a aresta alada
de BAUMGART [63], Doubly-Connected Edge List (DCEL) de PREPARATA e
SHAMOS [64] e a quad-edge de GUIBAS e STOLFI [65], as quais consomem aproxi-
madamente 27n, 18n e 36n referencias, respectivamente. Todas permitem acesso em
tempo O(1) a topologia da triangulacao. No caso da quad-edge, e possıvel realizar
consultas em tempo constante ate mesmo sobre o grafo dual.
Semi-Aresta
A introducao do conceito de semi-arestas deu-se em 1985 por Kevin Weiler para a
representacao de superfıcies poliedricas. Nesta estrutura, cada aresta e dividida em
duas semi-arestas com direcoes opostas, totalizando 6n− 12 semi-arestas por trian-
gulacao. Usualmente, uma implementacao desta estrutura utiliza quatro ponteiros
por semi-aresta para: o vertice de destino (ou de origem), a proxima semi-aresta
no sentido anti-horario pertencente a mesma face, a semi-aresta “gemea” da face
adjacente, e a face adjacente a esquerda. As arestas ordinarias ficam definidas de
modo implıcito por pares de semi-arestas “gemeas” entre si. Conclui-se entao que
sao necessarios n + 8(3n − 6) + (2n − 4) = 27n − 52 ≈ 27n ponteiros. Todas as
operacoes sao realizadas em tempo constante.
Arestas Direcionadas
CAMPAGNA et al. [66] propuseram um esquema denominado arestas direciona-
das. Esta estrutura fornece consultas sobre informacoes de adjacencia em tempo
constante, sendo exclusivamente apropriada para malhas triangulares. Uma carac-
terıstica interessante desta estrutura e a escalabilidade, advinda da capacidade de
gerenciar a relacao custo-benefıcio entre a velocidade de acesso e a quantidade de
memoria requerida. Esse mecanismo pode ser ativado sob demanda, guiado, por
exemplo, pelo tamanho da entrada e dos recursos disponıveis. No mınimo, pode-se
chegar a 13n referencias armazenadas.
21
2.6.3 Estruturas Baseadas em Vertice
Lista e matriz de incidencias
As estruturas de dados mais comuns para representar grafos explicitamente sao a
matriz de incidencias e a lista de incidencias. Uma matriz de incidencia de um grafo
G = (V,E) e uma matriz quadrada de ordem n, onde cada elemento e definido por:
A[i, j] =
1 se (vi, vj) ∈ E,
0 se (vi, vj) 6∈ E.
Cada elemento da matriz indica se um aresta particular pertence ao grafo. Consi-
derando grafos simples, sem a existencia de lacos, os elementos da diagonal principal
sao todos iguais a zero. No caso de grafos nao direcionados, a matriz de incidencias
e sempre simetrica. A representacao de grafos direcionados se da pela introducao de
um sinal negativo. Assim, os elementos das matrizes assumem valores no conjunto
{−1, 0, 1}. Nesta tese, ficaremos limitados aos grafos nao direcionados.
Dada uma matriz de incidencias, consultar a existencia de uma aresta entre dois
vertices requer tempo Θ(1), basta verificar se o valor do elemento correspondente
na matriz e nao nulo. O conjunto de todos os vizinhos de um dado vertice v e
determinado em tempo Θ(n) ao percorrer a linha (ou coluna) correspondente a v.
Observe que mesmo se um vertice possuir poucos vizinhos, e possıvel que tenhamos
que examinar todos os elementos da linha (ou coluna) correspondente.
Uma matriz de incidencias consome O(n2) bits, independente da quantidade de
arestas do grafo. Em se tratando de grafos densos, onde o numero de arestas e Θ(n2),
a matriz de incidencias pode ser considerada viavel. Sendo esta simetrica quando da
representacao de grafos nao direcionados, pode-se armazenar apenas os elementos
acima da diagonal, conduzindo para uma representacao da ordem de n(n−1)/2 bits.
Quando o numero de arestas e muito menor do que n2, no caso de grafos es-
parsos, a lista de incidencias e mais adequada. Em grafos esparsos, muitas vezes a
quantidade de arestas cai para O(n). Isto acontece no caso de malhas empregadas
22
em simulacoes pelo metodo dos elementos finitos, onde a relacao entre o grau de
um vertice e o numero total de vertices tende assintoticamente a zero. CLINE e
RENKA [67] foram um dos primeiros a utilizar uma estrutura baseada em listas de
incidencias para a construcao de triangulacoes de Delaunay.
Vertices estrelados
KALLMANN e THALMANN [68] desenvolveram uma estrutura de dados batizada
de vertices estrelados. Nesta, para cada vertice v armazena-se o grau de v e re-
ferencias aos seus vizinhos. Para cada vizinho v′ de v, armazena-se ainda um inteiro
que indica qual e o vertice vizinho de v′ tal que {v, v′, v′′} e um triangulo da malha.
Portanto, esta estrutura armazena cada aresta duas vezes, resultando em um total
de 7n referencias. As informacoes topologicas sao acessadas em tempo O(deg(v)).
Blandford et al
No esquema de representacao de BLANDFORD et al. [1], cada vertice guarda a
lista de seus vertices adjacentes, de modo analogo ao usado por CLINE e RENKA
[67]. Esta lista e representada por por uma concatenacao dos rotulos dos vertices.
Isto e o que na verdade os permite obter uma estrutura compacta. Ao inves de
armazenar o rotulo de cada vertice adjacente, eles armazenam as diferencas entre
o rotulo do vertice central e os rotulos de seus vertices adjacentes. Para garantir
que o tamanho dos rotulos das diferencas seja bem menor do que o tamanho de um
ponteiro, o grafo e renumerado utilizando um algoritmo baseado em separadores de
grafos. Ao final, sao necessarios 5 bytes por triangulo, o que representa um ganho
de 5 a 10 vezes em relacao as estruturas convencionais. Para triangulacoes com grau
limitado, esta estrutura suporta operacoes de travessia da vizinhanca de uma face,
insercao e remocao de triangulos em tempo constante.
A Tabela 2.1 contem um resumo das caracterısticas das estruturas de dados
apresentadas nesta secao. Tendo como objetivo a reducao do numero de referencias
utilizando a teoria de conjuntos transversais por vertice, o esquema descomprimido
23
Tabela 2.1: Numero de referencias utilizadas e custo de acesso a informacoes de
adjacencias em estruturas de dados para a representacao de triangulacoes 2D.
Estrutura de dados Numero de referencias Tempo de acesso
Sopa de triangulos 6n− 12 O(n)
Aresta alada 27n− 52 O(1)
DCEL 18n− 36 O(1)
Quad-edge 36n− 72 O(1)
Semi-aresta 27n− 52 O(1)
CGAL 13n− 4 O(1)
Vertices estrelados 7n− 12 O(deg(v))
Lista de incidencias ([1]∗; [67]) 6n− 12 O(deg(v))
∗ Considerando a versao descomprimida.
proposto por BLANDFORD et al. [1] e naturalmente o mais viavel para servir como
base de nossa estrutura. O fato de cada aresta ser representada quatro vezes, mesmo
em sua versao comprimida, torna-o susceptıvel a melhorias.
24
Capıtulo 3
Transversal por Vertice
Como anunciado anteriormente, utilizaremos conjuntos transversais de triangulos
por vertice para a construcao de uma representacao computacional de grafos maxi-
mais planares. Podemos adiantar que quanto menor o tamanho de um transversal,
maior sera a economia em espaco fornecido por nossa representacao. E primordial
entao estudar em detalhes suas propriedades combinatorias e algorıtmicas, de modo
a possibilitar uma maior compreensao das vantagens e limitacoes que seu uso pode
nos trazer.
3.1 Complexidade de Transversais por Vertice
Considere um grafo planar G arbitrario. Note que, qualquer que seja G, existe
ao menos um transversal de triangulos cuja construcao e trivial. Basta selecionar
um unico vertice de cada face triangular pertencente a G, enquanto houver faces
descobertas. No caso de grafos planares onde predominam faces de tamanho maior
do que tres, esta solucao pode ocasionalmente levar a um transversal de tamanho
exatamente igual a τ(G). Em grafos maximais planares, contudo, este algoritmo
raramente nos levara a uma solucao otima.
Ao considerar o emprego na pratica de transversais de triangulos, e preciso saber
se estamos lidando com um problema cuja solucao exata pode ser calculada de modo
eficiente. Caso contrario, precisaremos lancar mao de algoritmos arbitrarios, mas de
25
preferencia com alguma garantia sobre a aproximacao da solucao retornada.
Infelizmente, veremos que calcular transversais mınimos de grafos planares, ou
mesmo decidir se existe um transversal de tamanho k > 0, e uma tarefa difıcil. Mais
precisamente, demonstraremos que o problema Transversal de Triangulos por
Vertice nao e mais facil de ser solucionado do que uma variacao NP-completa do
3-Sat. A seguir, construiremos uma versao plana do dispositivo desenvolvido por
GROSHAUS et al. [49] na demonstracao do Teorema 2.9.
Teorema 3.1. Transversal de Triangulos por Vertice e NP-completo para
grafos planares com grau maximo 5.
Demonstracao. Este problema esta claramente em NP. Para provar sua NP-
dificuldade, uma instancia arbitraria de 3-Sat2+1 Planar sera transformada em
uma instancia de Transversal de Triangulos por Vertice cujo grafo de entrada
e planar.
Seja F uma instancia de 3-Sat2+1 Planar com variaveis x1, x2, . . . , xn e
clausulas C1, C2, . . . , Cm.
Variaveis. Para cada variavel xi, existira um subgrafo Gi emG tal como ilustrado
na Figura 3.1. Um transversal de Gi possui ao menos 3 vertices, devido existirem
tres triangulos disjuntos neste. Observe que se um dos vertices bi ou b′i pertencer a
um transversal juntamente com a′′i , entao serao necessarios outros dois vertices para
cobrir o restante dos triangulos. Note ainda que se ai fizer parte de um transversal no
qual b′′i pertence, sera possıvel troca-lo por bi sem alterar o tamanho do transversal.
Pelo mesmo motivo, e possıvel trocar a′i por b′i. Com isso, sempre serao selecionados
ai, a′i, a′′i ou bi, b
′i, b′′i .
Utilize os vertices bi, b′i e a′′i como conectores entre o subgrafo Gi e as clausulas
de F . Com efeito, se o literal xi (xi) ocorrer duas vezes em F , os vertices bi e b′i
corresponderao a estas ocorrencias e a′′i a ocorrencia de sua negacao xi (xi).
Clausulas. Para cada clausula Cj, j = 1, 2, . . . ,m, constroi-se um triangulo
cujos vertices sao dados pelos seus literais. Quando |Cj| = 2, adiciona-se um vertice
auxiliar. Para completar a reducao, faca k = 3n. A Figura 3.2 ilustra um exemplo
26
ai a′i
a′′i
bi b′i
b′′i
Figura 3.1: Subgrafo Gi correspondente a variavel xi.
desta construcao. Sera demonstrado a seguir que F e satisfatıvel se e somente se G
possui um transversal de triangulos de tamanho igual a 3n.
Suponha que F e satisfatıvel. Seja V ′ o transversal de triangulos a ser cons-
truıdo, inicialmente vazio. Se a variavel xi ocorre com valor verdadeiro em F ,
adicione {bi, b′i, b′′i } a V ′. Caso contrario, adicione {ai, a′i, a′′i }. E facil ver que todos
os triangulos de G estao cobertos e que |V ′| = 3n.
Agora, suponha que V ′ e um transversal de triangulos de G de tamanho igual a
3n. Desde que cada Gi possui 3 triangulos disjuntos e G possui n copias disjuntas
de Gi, V′ e irredutıvel. Como observado inicialmente, um transversal mınimo de Gi
pode ser dado por {ai, a′i, a′′i } ou {bi, b′i, b′′i }. Quando o primeiro subconjunto estiver
em V ′, atribua o valor verdadeiro para o literal de xi com uma unica ocorrencia.
Caso o segundo tenha sido selecionado, atribua o valor verdadeiro ao literal de xi
com duas ocorrencias.
Estudar restricoes de problemas intrataveis e importante para compreendermos
o que ha no limite entre P e NP. Normalmente, busca-se apresentar problemas que
possam ter sua dificuldade reduzida ao considerar diferentes classes para o grafo de
entrada. No caso do Transversal de Triangulos por Vertice, entretanto, foi
visto que sua restricao a grafos maximais planares nao e suficiente para torna-lo um
problema polinomialmente tratavel. O teorema a seguir contem uma demonstracao
deste fato, pela construcao de uma reducao polinomial a partir do Transversal de
Triangulos por Vertice em grafos planares.
27
x1
x1x1
x2
x2x2
x3
x3x3
x4
x4x4
C1
C4
C3
C2
Figura 3.2: Exemplo de grafo construıdo pela reducao apresentada no Teorema 3.1
para uma instancia de 3-Sat2+1 Planar dada por (x1 ∨ x2 ∨ x4) ∧ (x1 ∨ x3 ∨ x4) ∧(x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x2 ∨ x3).
Teorema 3.2. Transversal de Triangulos por Vertice e NP-completo em gra-
fos maximais planares.
Demonstracao. Um certificado para este problema e identico a um certificado para
o Transversal de Triangulos por Vertice ordinario. Logo, ele pertence a NP.
Sem perda de generalidade, a face infinita nao sera considerada na demonstracao.
Dado um grafo planar G, construa um grafo maximal planar G′ da seguinte maneira.
Para cada face nao triangular de G, crie uma aresta entre um par qualquer de
vertices de sua fronteira mais distantes entre si. Insira, nesta ordem, quatro vertices
na aresta nova: a′i, a′′i , b′′i e a′i. Ate este ponto, a face original fora dividida em duas
faces denominadas falsas. Adicione um vertice no centro de cada uma das faces
falsas, conectando-o aos vertices que delimitam o contorno da respectiva face. Pelo
mesmo motivo anterior, estes vertices e as novas faces sao denominados de falsos(as).
Respeitando o sentido anti-horario, denomine estes vertices de ai e bi. Denote por
V ∗ o conjunto de todos os vertices ai e bi, e faca ` = |V ∗|. Vale ressaltar que sempre
serao criados dois triangulos disjuntos por face. A Figura 3.3 contem um exemplo
desta construcao para uma face com 6 vertices.
28
ai
a′′i
a′i
b′i
b′′i
bi
Figura 3.3: Subdivisao de uma face hexagonal segundo a reducao apresentada no
Teorema 3.2.
Deve-se mostrar que existe um transversal de triangulos de tamanho ≤ k para G
se e somente se G′ possui um transversal de triangulos de tamanho ≤ k + 2`, onde
` e igual ao numero de faces nao triangulares de G.
Suponha que G possui um transversal de triangulos X de tamanho menor ou
igual a k. Seja X ′ = X ∪ V ∗. Entao, o conjunto X ′ e um transversal de triangulos
de G′. Para verificar isto, basta observar que todas as faces falsas sao cobertas pelo
conjunto V ∗, ao passo que as faces originais ja estao cobertas por X. Alem disso,
tem-se que |X ′| ≤ |X|+ |V ∗| ≤ k + 2`.
Assuma agora que existe um transversal X ′ de G′ de tamanho ≤ k + 2`. Note
que, para cada face subdividida como explicado inicialmente, um transversal de
triangulos mınimo e dado por {ai, bi}, ou {a′i, b′′i }, ou {a′i, b′′i }, exclusivamente. Com
isso, e sempre criar um transversal de G′ contendo apenas os vertices ai e bi, ou
seja, o conjunto V ∗. Com isso, as faces originais devem estar cobertas somente por
vertices verdadeiros. Logo, X = X ′ \ V ∗ e um transversal de G. Desde que V ∗
possui exatamente 2` vertices, entao |X| ≤ k.
3.2 Vigilancia de Terrenos com Guardas-Vertice
O primeiro resultado obtido sobre a dificuldade do Vigilancia de Terreno com
Guardas-Ponto e devido a COLE e SHARIR [21]. Segundo GHOSH [69], ainda
29
nao se sabe se o Vigilancia de Terreno com Guardas-Vertice ou o Vigilancia
de Terreno com Guardas-Aresta sao NP-difıceis (este ultimo sera abordado no
Capıtulo 4). Os resultados sobre Transversal de Triangulos por Vertice con-
tidos na Secao 3.1 nos possibilitaram responder de forma afirmativa esta questao.
A reducao a ser descrita produzira terrenos com O(n) faces, o que representa uma
melhoria sobre a demonstracao O(mn) de COLE e SHARIR [21].
Teorema 3.3. Vigilancia de Terreno com Guardas-Vertice e NP-difıcil.
Demonstracao. Seja G um grafo planar, e denote por T um terreno poliedrico ar-
bitrario construıdo a partir de G como a seguir. Antes de prosseguir, assumiremos
que e fornecida uma imersao de G no plano utilizando apenas arestas retas.
Para as faces nao triangulares de G, seguiremos a mesma construcao descrita
no Teorema 3.2. Adicionalmente, os vertices falsos sao deslocados para abaixo da
superfıcie como ilustrado na Figura 3.4.
Para completar a reducao, insira um ponto no centroide de cada face triangular
do grafo original G, aplique uma elevacao negativa, e conecte-o aos vertices do
contorno desta face.
Precisamos mostrar que G possui um transversal de triangulos por vertice de
tamanho k, se e somente se a cardinalidade mınima do conjunto de guardas-vertice
do terreno T e k+` vertices, onde ` e o numero de faces nao triangulares presentes em
G. Denote por V ∗ o conjunto de todos os vertices ai ou bi, escolhidos arbitrariamente.
Se X e um transversal mınimo para G de tamanho no maximo k, entao X ′ =
X ∪V ∗ e um conjunto de guardas-vertice de cardinalidade mınima para T . Observe
que o conjunto de guardas-vertice mınimo de cada face nao triangular deve conter
ai ou bi, pois nenhum outro vertice da face e capaz de enxergar toda sua superfıcie.
Desde que todo triangulo de G dara origem a uma depressao, e preciso selecionar
qualquer um dos vertices de cada face triangular de origem. Alem disso, temos que
|X ′| ≤ |X|+ |V ∗| ≤ k + `.
Para demonstrar a volta, basta descartarmos todos os vertices falsos de X ′.
30
ai
bi
b′i
b′′i
a′i
a′′i
(a)
b′′i
a′′i
b′i a′
i
biai
(b)
Figura 3.4: (a) Subdivisao e (b) secao transversal de uma face hexagonal apos a
reducao apresentada no Teorema 3.3.
3.3 Algoritmos para Transversais por Vertice
O Teorema 3.2, infelizmente, comprovou a inexistencia de algoritmos exatos de
tempo polinomial para o Transversal de Triangulos por Vertice em grafos
maximais planares. Como planejamos avalia-los na pratica, precisamos considerar
apenas algoritmos eficientes em tempo, mesmo que isto signifique uma diminuicao da
qualidade das solucoes calculadas. Apresentaremos, a seguir, quatro algoritmos po-
linomiais que possibilitam determinar transversais de cardinalidades mais proximas
do valor otimo de pior caso, que e de bn/2c vertices.
31
3.3.1 Algoritmo Otimo no Pior Caso
BOSE et al. [22] observaram que dada uma 2-coloracao policromatica de uma tri-
angulacao G, o menor conjunto de vertices de mesma cor desta coloracao e um
transversal para G. Alem disso, com base na observacao de que uma 2-coloracao
policromatica de um refinamento de um grafo G tambem e uma 2-coloracao com
faces policromaticas valida para G, os autores demonstraram que esta ideia poderia
ser aplicada para o calculo de transversais de grafos planares arbitrarios.
Uma 2-coloracao policromatica pode ser calculada utilizando um algoritmo de 4-
coloracao para grafos planares, como descrito na Secao 2.1.1. Contudo, o algoritmo
de 4-coloracao mais eficiente ate o presente momento tem custo O(n2) [70]. Um
modo de evitar a utilizacao deste algoritmo de custo quadratico seria recorrer a um
esquema baseado em 5-coloracoes, pois estas podem ser calculadas em tempo linear
para grafos planares [71]. Neste caso, selecionaremos no maximo b3n/5c vertices
para o transversal.
O Teorema de Petersen sobre emparelhamentos perfeitos em grafos 3-regulares
(Teorema 2.5) tambem permite obter um algoritmo de tempo O(n) [22]. O resultado
a seguir revela a relacao entre uma 2-coloracao policromatica de uma triangulacao
planar G e um emparelhamento perfeito de seu grafo dual G∗. Incluımos sua de-
monstracao aqui na tentativa de manter a completude do presente trabalho.
Lema 3.1 ([22]). Sejam dados uma triangulacao G, seu grafo dual G∗, e uma
2-coloracao policromatica de G. Defina MC como o conjunto das faces mono-
cromaticas de G. Entao:
1. O conjunto MC∗ = {e∗ : e ∈MC} e um emparelhamento perfeito em G∗;
2. Existe uma 2-coloracao policromatica de G cujas arestas monocromaticas coin-
cidem com o conjunto {e : e∗ ∈M∗}, onde M∗ e um emparelhamento perfeito
em G∗.
Demonstracao. Se e∗1, e∗2 ∈ MC∗, entao e1, e2 ∈ MC. Como nao existem faces
monocromaticas em G, e1 e e2 nao podem pertencer a um mesmo triangulo de G.
32
Logo, e∗1 e e∗2 nao compartilham vertices em MC∗. Suponha agora que exista um
vertice f ∗ ∈ G∗ que nao e tocado por arestas em MC∗. Entao, f ∈ G nao possui
arestas monocromaticas. Entretanto, e impossıvel colorir triangulos com duas cores
sem o aparecimento de arestas monocromaticas. Logo, MC∗ e um emparelhamento
perfeito.
Seja M∗ um emparelhamento perfeito em G∗ e M o conjunto de arestas de G
que sao duais as arestas em M∗. Defina o grafo G′ como sendo igual a G sem as
arestas pertencentes a M . Assim, todas as faces de G′ formam ciclos de tamanho
4. Portanto, G′ e bipartido e admite uma 2-coloracao. Visto que cada aresta mono-
cromatica em M da origem a dois triangulos em G, esta coloracao induz ainda uma
2-coloracao policromatica de G.
Sabe-se que o grafo dual de uma triangulacaoG e 3-regular e biconexo, assumindo
que existe um vertice fictıcio no infinito conectado a todos os vertices do fecho
convexo de G. O Teorema de Petersen (Teorema 2.5) assegura a existencia de um
emparelhamento perfeito para este grafo. Logo, pelo Lema 3.1, toda triangulacao
possui uma 2-coloracao policromatica. Com base nisto, o algoritmo de BOSE et al.
[22] e dividido nos seguintes passos:
1. Construa o grafo dual G∗ de G.
2. Calcule um emparelhamento perfeito M∗ de G∗.
3. Construa um grafo G′ utilizando o mesmo conjunto de vertices de G, mas
cujas arestas sao apenas aquelas que restarem apos a remocao das arestas de
G duais as saturadas por M∗.
4. Calcule uma 2-coloracao de G′.
5. Retorne os vertices pertencentes ao conjunto de cores de menor cardinalidade.
O passo mais caro deste algoritmo e a determinacao de um emparelhamento
perfeito do grafo dual. Recentemente, foi desenvolvido um algoritmo que calcula
emparelhamentos maximos de grafos planares 3-regulares biconexos em tempo O(n)
33
(ver Secao 2.1.2). Concluımos assim que o algoritmo realiza todas suas operacoes
em tempo linear.
Desde que nenhum vertice do grafo original G e removido e G′ e biconexo, o
numero de vertices selecionados para o transversal sera bn/2c.
3.3.2 Algoritmo Guloso
Dada uma triangulacao G, considere a seguinte heurıstica gulosa. Seja X um con-
junto inicialmente vazio. Enquanto o conjunto F (G) for nao vazio, selecione um
vertice v de V (G)\X cujo numero de faces incidentes ainda nao cobertas por mem-
bros de X e maximal. Adicione v ao conjunto X e remova de G todas as faces
f ∈ F (G) incidentes em v.
Uma face so e removida de F (G) se um de seus vertices for selecionado. Assim,
este algoritmo sempre calcula um transversal valido. Alem disso, veremos experi-
mentalmente que ele sempre retorna transversais cujas cardinalidades sao otimas no
pior caso.
Conjectura 3.1. Dada uma triangulacao arbitraria G, o algoritmo guloso calcula
um transversal de triangulos por vertice de tamanho no maximo igual a bn/2c.
3.3.3 Algoritmos Randomizados
Sabemos que, no pior caso, precisaremos selecionar bn/2c vertices para cobrir to-
das as faces de uma triangulacao [55]. Entao, um algoritmo arbitrario cuja solucao
fique sempre um pouco acima deste limite pode ser considerado uma opcao viavel.
Ainda mais se este for facilmente implementado e reduzir consideravelmente o tempo
de CPU gasto em comparacao com o de seus concorrentes. A seguir, apresentare-
mos algumas heurısticas que calculam transversais empregando decisoes randomicas.
Apesar de nao possuırem garantias teoricas fortes, estes servirao para demonstrar
que nao e difıcil se aproximar do limite de bn/2c.
34
Probabilidade Constante
Seja G uma triangulacao arbitraria. Considere um conjunto X inicialmente vazio
e faca S = σ(F (G)), onde σ e uma permutacao randomica. (i) Enquanto S for
diferente de ∅, selecione uma face f de S; (ii) se um dos vertices de f estiver em
X, descarte f e retorne para o passo (i); (iii) caso contrario, selecione um de seus
vertices com probabilidade 1/3 e adicione-o a X; (iv) faca S = S \ {F} e retorne
para (i).
O valor esperado do grau de um vertice v em uma triangulacao G e E[deg(v)] =
1n
∑u∈V deg(u) = (6n− 12)/n. Assim, um vertice arbitrario de G cobre, em media,
seis arestas pertencentes ao conjunto E(G), sem considerar os vertices previamente
selecionados. Entao o tamanho esperado de um transversal E[k] calculado por este
algoritmo e dado por:
E[k] =3n− 6
E [deg(v)]= n/2.
Probabilidade Variavel
No algoritmo anterior, a escolha randomica era realizada utilizando um sorteio justo,
onde a probabilidade de um vertice ser selecionado nao dependia da estrutura do
grafo em consideracao. Utilizaremos aqui um sorteio com probabilidades diferentes
para cada face. Dada uma face f ∈ F (G), a probabilidade de um vertice v de
f ser escolhido para o transversal e dada por deg(v)/∑
v∈f deg(v). O restante do
algoritmo e exatamente como o de probabilidades constantes.
3.3.4 Uma 3-aproximacao
Um algoritmo k-aproximativo para o problema de transversal de ciclos de tama-
nho k em grafos arbitrarios nos fornecera uma 3-aproximacao para o transversal de
triangulos por vertice.
Teorema 3.4 ([49]). Uma solucao aproximada para o problema de transversal de
triangulos por vertice mınimo de um grafo maximal planar G pode ser calculada em
35
tempo O(n) e o tamanho da solucao e no maximo 3 vezes o valor otimo.
Demonstracao. Sejam dados um grafo maximal planar G e dois conjuntos vazios
quaisquer X e H. (i) Enquanto houver triangulos descobertos em G, (ii) selecione
uma face f ; (iii) coloque os vertices de f em X e, em seguida, mova f para a colecao
H; (iv) remova de E(G) todas as arestas incidentes nos vertices de f .
O conjunto H e claramente um empacotamento de triangulos em G, enquanto X
e um transversal de triangulos. Seja OPT a cardinalidade mınima de um transversal
para G. Entao, OPT ≥ |H|. Alem do mais, |X| = 3|H|. Logo, |X| ≤ 3 OPT.
E possıvel demonstrar ainda que esta aproximacao tambem pode ser obtida por
um algoritmo de 4-coloracao do grafo dual. Para tanto, dada uma triangulacao G,
denote por G∗ seu grafo dual. Como o grafo G∗ e 3-regular, entao existe uma 4-
coloracao propria dos vertices de G∗. Seja {V ∗1 , V ∗2 , V ∗3 , V ∗4 } a particao dos vertices
de G∗ induzida por esta 4-coloracao. Faca X∗ igual ao conjunto de {V ∗1 , V ∗2 , V ∗3 , V ∗4 }com cardinalidade mınima. Claramente, |X∗| ≤ n/4. Dado um conjunto X inicial-
mente vazio, adicione em X os vertices de cada face f ∈ F (G) tal que f ∗ pertenca
a X∗. Logo, |X| ≤ 3|X∗|. Se OPT e a cardinalidade mınima de um transversal de
triangulos de G, entao OPT ≤ |X∗|. Logo, pode-se concluir que |X| ≤ 3|OPT |.Como n/3 ≤ OPT ≤ bn/2c, esta aproximacao nos garante somente que o tama-
nho do transversal e menor ou igual a n, o que e insuficiente. Entretanto, veremos
experimentalmente que este numero e estritamente menor do que n.
3.4 Resultados Experimentais
Os algoritmos apresentados na Secao 3.3 foram implementados em C++, utilizando
a Standard Template Library (STL). Os testes foram realizados em um computador
com processador Intel Core i7 840QM 64-bit (codinome Clarksfield) possuindo 4
nucleos com 1,87 GHz de clock e 4GB de RAM DDR3 de 1333 MHz. Este processa-
dor, pertencente a classe de microarquitetura Nehalem, possui quatro caches L2 de
256 KB e um cache L3 compartilhado de 8 MB. Os executaveis foram criados com
36
o compilador g++, versao 4.4.4, habilitando as opcoes de compilacao -O3, -DNDEBUG
e -frounding-math.
As implementacoes foram avaliadas em triangulacoes de Delaunay de quatro tipos
de distribuicoes de pontos no plano, com tamanhos entre 100 mil e 8 milhoes. Foram
consideradas uma distribuicao uniforme no interior de um quadrado unitario, distri-
buicao uniforme no interior de um cırculo unitario, uma distribuicao normal simples
e uma distribuicao normal ponderada com uma maior concentracao de pontos ao
longo do eixo x. Dada uma distribuicao normal arbitraria, sua forma ponderada e
dada pela seguinte transformacao f(x, y) = (y, b/(x − bx + b)), com b = 0,005. A
Figura 3.5 contem ilustracoes destas distribuicoes.
A biblioteca CGAL 3.7 [25] foi utilizada para auxiliar na construcao de trian-
gulacoes de Delaunay dos conjuntos de pontos sobre as quais os algoritmos foram tes-
tados. Esta biblioteca e desenvolvida utilizando conceitos de programacao generica
de modo tal que todos os seus algoritmos sao parametrizados pelo nucleo geometrico
de base, o qual deve conter definicoes desde a representacao de numeros (inteiros,
ponto flutuante, de precisao arbitraria, etc.) a construcao de objetos e predicados
geometricos. Utilizamos o nucleo Exact predicates inexact constructions -
kernel, pois este possibilita o tratamento de conjuntos de pontos com configuracoes
degeneradas, como e o caso de quatro pontos co-circulares para a triangulacao de
Delaunay, ainda que mantendo um desempenho razoavel. Os tempos de CPU apre-
sentados nesta secao foram obtidos com o auxılio da classe CGAL::Timer.
O desempenho do algoritmo de BOSE et al. [22] foi limitado pelo tempo con-
sumido na determinacao do emparelhamento perfeito do grafo dual a uma trian-
gulacao. Apesar de existir um algoritmo de tempo O(n) capaz de calcular estes
emparelhamentos (ver Secao 2.1.2), na pratica isto se demonstrou bem diferente.
As implementacoes mais difundidas em C++ para determinar emparelhamentos de
cardinalidade maxima fazem parte das bibliotecas Boost [72] e LEDA [73]. Ambas
empregam o algoritmo de EDMONDS [38] (aperfeicoado por GABOW e TARJAN
[41]) para grafos arbitrarios, cuja complexidade e O(nm · α(n,m)), onde α e a
37
(a) Uniforme em quadrado. (b) Uniforme em disco.
(c) Normal. (d) Normal ponderada.
Figura 3.5: Ilustracao das distribuicoes de pontos no plano utilizadas para avaliar
os algoritmos de transversais de triangulos por vertice.
38
inversa da funcao de Ackermann. Neste trabalho, utilizamos a funcao edmonds -
maximum cardinality matching da bibioteca Boost versao 1.41.0. Na Tabela 3.1,
sao apresentados a razao de vertices selecionados para o transversal e o tempo gasto
por cada um de seus passos. O tempo total que o algoritmo gastou em uma trian-
gulacao com 500 mil vertices foi em torno de 25 minutos, o qual e dominado pelo
calculo do emparelhamento. Face ao seu elevado custo, este algoritmo foi avaliado
apenas para conjuntos de pontos com tamanhos entre 100 e 500 mil.
Lembre-se que o numero policromatico p(G) de uma triangulacao so pode assumir
os valores 2 ou 3, onde p(G) = 3 se e somente se G for Euleriana, pois pode-se
demonstrar que uma 3-coloracao policromatica e equivalente a uma 3-coloracao dos
vertices de G. O menor transversal de uma triangulacao arbitraria obtido por um
algoritmo empregando uma 2-coloracao policromatica e entao bn/2c. Isto explica a
tendencia a transversais com bn/2c vertices apresentada na Tabela 3.1
As Figuras 3.6a, 3.7a, 3.8a e 3.9a contem os tempos de processamento gastos
pelos demais algoritmos em cada uma das quatro distribuicoes com tamanhos de
500 mil a 8 milhoes. Como era de se esperar, o algoritmo 3-aproximativo foi o mais
rapido dentre todos, pois este percorre a triangulacao de modo arbitrario e o custo
de sua decisao para selecionar um vertice do transversal e bastante baixo. Alem
disso, cada iteracao deste algoritmo cobre mais faces do que a de qualquer outro.
Observe que mesmo o mais lento destes tres algoritmos e cerca de 600 vezes mais
rapido do que o algoritmo de 2-coloracao policromatica [22].
A implementacao do algoritmo guloso requereu a manutencao de um heap binario
maximo dos vertices cuja chave de ordenacao e dado pelo numero de faces nao co-
bertas incidentes em cada vertice. A cada vertice selecionado para o transversal,
e preciso reduzir em duas unidades o numero de faces cobertas por seus vertices
vizinhos. Um heap possibilita atualizar estes valores em tempo O(log n). Com
isso, a complexidade de nossa implementacao do algoritmo guloso e O(n log n), en-
quanto que o custo dos algoritmos randomizados e da 3-aproximacao e claramente
O(n). Contudo, o desempenho das implementacoes dos algoritmos randomizados
39
foi inferior ao do guloso. Isto e causado pelo padrao de acesso aleatorio as faces da
triangulacao destes algoritmos, o que resulta em mais acessos a memoria RAM. Este
fato esta nitidamente representado nas Figuras 3.6a, 3.7a, 3.8a e 3.9a.
Observe nas Figuras 3.6b, 3.7b, 3.8b e 3.9b que a taxa de vertices no transver-
sal permaneceu estavel em todas as distribuicoes de pontos examinadas para cada
algoritmo.
Conforme apresentado nas Figuras 3.6b, 3.7b, 3.8b e 3.9b, a Conjectura 3.1 e sa-
tisfeita experimentalmente. Na verdade, os transversais determinados pelo algoritmo
guloso contem em torno de 42% dos vertices do grafo. Os transversais calculados
pelos dois algoritmos randomizados ficaram abaixo de 55%, com uma ligeira vanta-
gem de 1% para a versao ponderada. O algoritmo 3-aproximativo obteve os piores
transversais, convergindo para uma taxa em torno de 77%.
40
Tabela 3.1: Tempos de CPU em segundos gasto por cada etapa do algoritmo de
2-coloracao policromatica e razao entre o tamanho de um transversal X e o numero
de vertices da triangulacao de diferentes distribuicoes de pontos.
Distribuicao |X|/nTempo de CPU (segundos)
G∗ M∗ 2-coloracao Total
Uniforme em quadrado
100 K 0.499775 0.216967 63.6993 0.32395 64.2402
200 K 0.499943 0.410937 245.145 0.673898 246.23
300 K 0.499972 0.608907 542.974 0.917861 544.501
400 K 0.499986 0.788881 992.645 1.2878 994.722
500 K 0.499861 1.00585 1564.8 1.58776 1567.39
Uniforme em cırculo
100 K 0.499095 0.208968 63.8453 0.337948 64.3922
200 K 0.499773 0.408937 246.146 0.640903 247.195
300 K 0.499815 0.602908 547.641 0.979851 549.224
400 K 0.499741 0.756885 994.458 1.24381 996.459
500 K 0.499949 0.984851 1566.61 1.65075 1569.25
Normal em quadrado
100 K 0.499985 0.225965 63.6433 0.330949 64.2002
200 K 0.499973 0.410938 245.821 0.643902 246.875
300 K 0.499912 0.59291 544.551 0.932858 546.077
400 K 0.499839 0.769883 996.647 1.22481 998.642
500 K 0.499933 0.975852 1553.52 1.62875 1556.13
Normal ponderada
100 K 0.499875 0.224966 63.8343 0.412937 64.4722
200 K 0.499638 0.451931 250.836 0.811876 252.1
300 K 0.499992 0.628905 559.211 1.19782 561.038
400 K 0.499734 0.815876 1013.14 1.41878 1015.38
500 K 0.499941 1.05084 1580.66 1.78273 1583.49
41
0
5
10
15
20
25
30
35
40
45
500 K 1 M 2 M 4 M 6 M 8 M
Tem
po d
e C
PU
(se
gund
os)
Número de Vértices
3-aproximaçãoguloso
randomizadorandomizado ponderado
(a)
0
0.25
0.5
0.75
1
1.25
500 K 1 M 2 M 4 M 6 M 8 M
Tam
anho
Rel
ativ
o do
Tra
nsve
rsal
Número de Vértices
3-aproximaçãoguloso
randomizadorandomizado ponderado
(b)
Figura 3.6: (a) Tempo de CPU gasto por cada algoritmo para determinar trans-
versais de triangulos e sua (b) razao de vertices selecionados para triangulacoes de
pontos distribuıdos uniformemente no interior de um quadrado unitario.
42
0
5
10
15
20
25
30
35
40
45
500 K 1 M 2 M 4 M 6 M 8 M
Tem
po d
e C
PU
(se
gund
os)
Número de Vértices
3-aproximaçãoguloso
randomizadorandomizado ponderado
(a)
0
0.25
0.5
0.75
1
1.25
500 K 1 M 2 M 4 M 6 M 8 M
Tam
anho
Rel
ativ
o do
Tra
nsve
rsal
Número de Vértices
3-aproximaçãoguloso
randomizadorandomizado ponderado
(b)
Figura 3.7: (a) Tempo de CPU gasto por cada algoritmo para determinar trans-
versais de triangulos e sua (b) razao de vertices selecionados para triangulacoes de
pontos distribuıdos uniformemente no interior de um cırculo unitario.
43
0
5
10
15
20
25
30
35
40
45
500 K 1 M 2 M 4 M 6 M 8 M
Tem
po d
e C
PU
(se
gund
os)
Número de Vértices
3-aproximaçãoguloso
randomizadorandomizado ponderado
(a)
0
0.25
0.5
0.75
1
1.25
500 K 1 M 2 M 4 M 6 M 8 M
Tam
anho
Rel
ativ
o do
Tra
nsve
rsal
Número de Vértices
3-aproximaçãoguloso
randomizadorandomizado ponderado
(b)
Figura 3.8: (a) Tempo de CPU gasto por cada algoritmo para determinar trans-
versais de triangulos e sua (b) razao de vertices selecionados para triangulacoes de
pontos normalmente distribuıdos no interior de um quadrado unitario.
44
0
5
10
15
20
25
30
35
40
45
50
500 K 1 M 2 M 4 M 6 M 8 M
Tem
po d
e C
PU
(se
gund
os)
Número de Vértices
3-aproximaçãoguloso
randomizadorandomizado ponderado
(a)
0
0.25
0.5
0.75
1
1.25
500 K 1 M 2 M 4 M 6 M 8 M
Tam
anho
Rel
ativ
o do
Tra
nsve
rsal
Número de Vértices
3-aproximaçãoguloso
randomizadorandomizado ponderado
(b)
Figura 3.9: (a) Tempo de CPU gasto por cada algoritmo para determinar trans-
versais de triangulos e sua (b) razao de vertices selecionados para triangulacoes de
pontos distribuıdos segundo a distribuicao normal ponderada.
45
Capıtulo 4
Transversal por Aresta
Motivados pela existencia de uma relacao entre conjuntos transversais de grafos
e problemas de galeria de arte, estudaremos neste capıtulo uma outra variante de
transversal denominada transversal por aresta. Antes de passarmos ao estudo destes
transversais, introduziremos uma definicao generalizada na qual tanto as entidades
que farao parte do transversal quanto aquelas que serao guardadas pelas primeiras
poderao assumir diversos formatos. Definiremos transversais por aresta como sendo
um caso particular desta generalizacao.
Seja G um grafo simples arbitrario. Dada uma famılia H de grafos, um H-
subgrafo de G e um subgrafo induzido de G isomorfo a um elemento de H. Considere
agora uma outra famılia F de grafos, de onde “recrutaremos” nossos guardas. Uma
colecao X de F -subgrafos de G e um (F,H)-transversal de G se todo H-subgrafo
em G e interceptado por membros de X. Quando F e composto por um vertice,
o conjunto X e denominado abreviadamente de H-transversal ou transversal por
vertice. No Capıtulo 3, estudamos H-transversais onde H era constituıdo apenas
por ciclos de tamanho tres, o qual foi convenientemente denominado de transversal
de triangulos.
Define-se entao um transversal por aresta (ou (K2, H)-transversal) de G como
sendo qualquer subconjunto das arestas de G que intercepte todos os H-subgrafos
existentes em G. Estamos interessados em transversais cuja famılia de subgrafos
interceptada H e igual a {K3}, os (K2, K3)-transversais ou transversais de triangulos
46
(a)
(b)
Figura 4.1: (a) Exemplo de grafo planar G e (b) um transversal de triangulos por
aresta de G de tamanho 2. As arestas mais espessas desenhadas em vermelho e azul
pertencem ao transversal. As regioes hachuradas representam as faces cobertas por
cada uma destas arestas.
por aresta. A Figura 4.1 contem um exemplo de transversal de triangulos por aresta
de um grafo maximal planar com 9 vertices. Note que e impossıvel utilizar menos
do que duas arestas para tocar todas as faces do grafo.
O problema de calcular um transversal por aresta de tamanho mınimo e abordado
neste capıtulo. Na verdade, consideramos o problema de decisao associado:
Transversal de Triangulos por Aresta
Entrada: Grafo G e inteiro positivo k.
Questao: Existe um transversal de triangulos por aresta de G com tamanho no
maximo k?
47
Mostraremos que o Transversal de Triangulos por Aresta e NP-completo
em grafos planares e grafos maximais planares. Os resultados contidos neste capıtulo
foram apresentados no European Workshop of Computational Geometry, EuroCG
2010, em Dortmund, sob o tıtulo “On the complexity of the edge guarding problem”
[26].
4.1 Complexidade de transversais por aresta
Primeiramente, mostraremos que o Transversal de Triangulos por Aresta res-
trito a grafos planares e tao difıcil de se resolver quanto a uma instancia de 3-Sat2+1
Planar, o qual e NP-completo pelo Lema 2.1. As demonstracoes a seguir fazem
uso da nocao de independencia entre subgrafos. Dado um grafo arbitrario G, dois
subgrafos G1 e G2 de G sao independentes se estes forem disjuntos por vertice e nao
existir nenhuma aresta em G ligando G1 a G2. Uma colecao de subgrafos de G e
dita independente se seus membros forem dois-a-dois independentes.
Teorema 4.1. Transversal de Triangulos por Aresta e NP-completo para gra-
fos planares de grau maximo igual a 5.
Demonstracao. E facil ver que ele pertence a NP. Para demonstrar sua NP-
dificuldade, considere uma instancia F de 3-Sat2+1 Planar com variaveis x1, x2,
. . . , xn e clausulas C1, C2, . . . , Cm.
Variaveis. Para cada variavel xi, associamos um subgrafo Gi em G, conforme
ilustrado na Figura 4.2a. Note que qualquer transversal de Gi possui ao menos 3
arestas, pois este possui um maximo de tres triangulos independentes. Observe que
caso bi ou b′i pertenca a um transversal acompanhadas de a′′i , entao sera necessario
utilizar uma aresta adicional, e.g., b′i, de modo a cobrir os outros triangulos des-
cobertos. Alem disso, se ai pertence ao mesmo transversal que b′′i , entao sempre
podemos substituir ai por bi sem alterar o tamanho do transversal. O mesmo ocorre
para a′i e b′i. Deste modo, sempre sera possıvel selecionar qualquer um dos conjuntos
{ai, a′i, a′′i } ou {bi, b′i, b′′i }.
48
bi b′i
b′′i
a′′i
ai a′i
(a)
x1 x1
x1x2
x2x2 x3 x3 x4 x4
x4x3
C4
C2
C1
C3
(b)
Figura 4.2: (a) Subgrafo Gi associado com a variavel xi. (b) Esquema do grafo
associado resultante a formula de 3-Sat2+1 Planar (x1 ∨ x2 ∨ x4)∧ (x1 ∨ x3 ∨ x4)∧(x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x2 ∨ x3).
Os vertices superiores das arestas bi e b′i, e qualquer vertice da aresta a′′i sao
usados como conectores entre Gi e as clausulas de da formula F . Alem disso, se
xi (resp. xi) ocorre duas vezes em F entao as arestas bi e b′i correspondem a estas
ocorrencias e a aresta a′′i a ocorrencia de sua negacao xi (resp. xi).
Clausulas. Para cada clausula Cj, j = 1, 2, . . . ,m, construa um triangulo cu-
jos vertices representam seus literais. Quando a clausula possui apenas dois lite-
rais, simplesmente adicionamos um vertice artificial, desde que isto nao influen-
cia qualquer atribuicao de valores verdade. Para finilizar a reducao, faca k igual
a 3n. A Figura 4.2b contem o grafo resultante da reducao aplicada a formula
49
(x1 ∨ x2 ∨ x4) ∧ (x1 ∨ x3 ∨ x4) ∧ (x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x2 ∨ x3). A seguir, sera
mostrado que F e satisfatıvel se e somente se G possui um transversal de triangulos
por aresta de tamanho exatamente igual a 3n.
Primeiro, suponha que F e satisfatıvel. Seja X um conjunto transversal inicial-
mente vazio. Se a variavel xi ocorre duas vezes com valor verdade em F , inserimos
{bi, b′i, b′′i } em X. Caso contrario, tomamos {ai, a′i, a′′i }. E facil ver que todo triangulo
em G e coberto por X e que |X| = 3n.
Agora, suponha que X e um transversal de trangulos por aresta de G de tamanho
3n. Desde que cada subgrafo Gi possui no maximo 3 triangulos independentes
e G possui n copias independentes de Gi, o conjunto X e irredutıvel. O menor
transversal de Gi pode ser ou {ai, a′i, a′′i } ou {bi, b′i, b′′i }. Se o primeiro subconjunto for
selecionado, atribuımos verdade aos literais xi de ocorrencia unica. Caso contrario,
atribuımos verdade aos literais xi com ocorrencia dupla.
Dado um grafo planar G, poderıamos considerar um algoritmo que inicialmente
construısse uma triangulacao G′ de G e determinasse um transversal por aresta X ′ de
G′. Desde que G′ e um refinamento de G, entao toda face de G′ esta contida em uma
face de G. Com efeito, o conjunto X = X ′ seria um transversal de G. Contudo,
demonstraremos a seguir que o calculo de um transversal por aresta mınimo em
grafos maximais planares pode ser considerado uma tarefa computacional tao difıcil
quanto em grafos planares arbitrarios.
Teorema 4.2. Transversal de Triangulos por Aresta e NP-completo para gra-
fos maximais planares.
Demonstracao. Seja G um grafo planar arbitrario. A demonstracao consiste em
transformar G em um grafo maximal planar G′ cujo transversal de triangulos por
aresta fica trivialmente determinado a partir de qualquer transversal para G.
Os triangulos em G sao mantidos intactos, enquando todas as outras faces sao
trianguladas como a seguir. Seja f = (v1, v2, . . . , vs) uma face em G de tamanho
s > 3. Iniciamos pela divisao de f em dois ciclos atraves de um caminho ligando
50
os vertices v1 e vbs/2c+1. Este caminho e composto por 8 arestas, a seber, (v1, u1),
(u1, u2), . . . , (u7, vbs/2c+1). Isto implica na criacao de dois ciclos Cr e Cl contendo
bn/2c+ 8 e n−bn/2c+ 8 vertices cada. No interior do ciclo Cr (resp. Cl), inserimos
os vertices r1 e r2 (resp. l1 e l2), os quais sao posteriormente conectados aos vertices
{v1, v2, . . . , vbs/2c+1} ∪ {u1, u2, u6, u7} e {vbs/2c+1, vbs/2c+2, . . . , v1} ∪ {u2, u3, . . . ,
u6}, respectivamente. A Figura 4.3 ilustra esta construcao para faces de tamanho 4
e 5. Todos os vertices, arestas e faces criados durante este processo sao denominados
falsos. Caso contrario, estas serao denominadas verdadeiras.
Denote por ` o numero de faces nao-triangulares deG, e sejaG′ um grafo maximal
planar resultante do processo de construcao que acabamos de descrever. Dado um
inteiro positivo qualquer k, afirmamos que G possui um transversal de triangulos
por aresta de tamanho no maximo k se e somente se G′ possui um transversal por
aresta cujo tamanho nao excede k + 2`.
Suponha que X e um transversal por aresta para G de tamanho k. Seja X ′ =
X∪E∗, onde E∗ e o conjunto de todas as arestas de tipo (r1, r2) e (l1, l2) (ver Figura
4.3). Afirmamos que X ′ e um transversal por aresta de G′. Primeiro, observe que
todo face falsa possui um vertice em E∗, enquanto as verdadeiras sao tocadas por
elementos de X. Alem disso, vale a seguinte desigualdade: |X ′| ≤ |X|+|E∗| ≤ k+2`.
Podemos agora assumir que existe um transversal por aresta X ′ para G′ de ta-
manho no maximo k + 2`. Obviamente, mesmo se todas as arestas verdade forem
selecionadas, existirao faces por cobrir (ver as areas nao hachuradas indicadas na
Figura 4.3). A observacao chave e que, em qualquer ciscunstancia, podemos sempre
escolher as arestas pertencendo ao conjunto E∗. Deste modo, faces verdade devem
estar cobertas apenas por arestas verdade. Por esta razao X = X ′ \E∗ e um trans-
versal por aresta de G. Desde que E∗ possui exatamente 2` arestas, a desigualdade
|X| ≤ k e valida.
51
v1 v4
v3v2
u1
u2
u3
u4u5
u6
u7
(a)
v2
v1v3
v4 v5
l1
l2
r1
r2
u7u6
u5 u4u3
u2 u1
(b)
Figura 4.3: Exemplos de construcoes de triangulacoes para faces consistindo de (a) 4
vertices e (b) 5 vertices. As areas hachuradas indicam os unicos triangulos cobertos
por arestas com extremidades no ciclo mais externo.
4.2 Vigilancia de Terrenos por Guardas-aresta
Assim como assumido no Capıtulo 3, usaremos o fato de que se um terreno poliedrico
triangulado for convexo, entao a regiao de visibilidade de qualquer vertice fica limi-
tada as suas faces incidentes. Deste modo, o calculo de um conjunto de guardas-
aresta para vigiar um terreno T pode ser reduzido a determinacao de um transversal
de triangulos por aresta da triangulacao subjacente a T .
Baseado na demonstracao para guardas-ponto desenvolvida por COLE e SHA-
RIR [21], ZHU [24] demonstrou que e NP-completo calcular um conjunto de guardas-
aresta mınimo. Entretanto, assim como na demonstracao de origem, esta tambem
requer a construcao de terrenos com O(mn) faces resultantes de uma reducao a par-
tir de instancias de 3-Sat. Com base nos Teoremas 4.1 e 4.2, desenvolvemos uma
reducao polinomial de baixo custo que produz terrenos com uma quantidade linear
de faces.
Teorema 4.3. Vigilancia de Terreno com Guardas-Aresta e NP-difıcil.
Demonstracao. Dado um grafo maximal planar G, construımos um terreno T como
a seguir. Para cada face f em G, insira um ponto p no seu centroide e conecte-o aos
52
vertices do contorno de f . Entao, translade levemente p por h unidades na direcao
do eixo z, com h < 0. Cada face levara ao aparecimento de exatamente uma pequena
depressao no terreno. Por conveniencia, as novas arestas sao rotuladas de falsas e
as antigas, pertencentes ao grafo de entrada, sao denominadas de verdadeiras.
Seja X um transversal de triangulos por aresta qualquer de G de tamanho k > 0.
Entao a colecao X e um transversal de triangulos por aresta de G se, e somente se,
esta for tambem um conjunto de guardas aresta de T de tamanho k.
Desde que toda depressao em T pode ser completamente vista de sua borda,
as arestas em X sao sempre suficientes para cobrir o terreno T inteiro construıdo
anteriormente. Suponha agora que X ′ e um conjunto de guardas-aresta arbitrario
para T calculado por um algoritmo qualquer, por exemplo, um algoritmo do tipo
guloso. Classifique as arestas em X ′ como verdadeiras ou falsas. Note que qualquer
aresta verdadeira em X ′ cobre ao menos o mesmo numero de faces que uma falsa.
Deste modo, e provavel que uma solucao otima para T consista apenas de arestas
verdadeiras. Caso contrario, observe que podemos sempre identifica e substituir
uma aresta falsa em X ′ por qualquer aresta verdadeira incidente. Logo, o conjunto
X = X ′ e um transversal de triangulos por aresta de G.
53
Capıtulo 5
Representacao de triangulacoes
bidimensionais
Ate o presente momento, estivemos concentrados na caracterizacao do problema de
conjuntos transversais de triangulos, tanto por vertice (Capıtulo 3) quanto por aresta
(Capıtulo 4). Apresentamos resultados sobre a dificuldade em calcular conjuntos
transversais mınimos e como isto pode nos auxiliar a provar alguns fatos interessantes
sobre o problema de vigilancia em terrenos poliedricos. Neste capıtulo, mostraremos
que e possıvel servir-se do conceito de conjunto transversal de triangulos por vertice
para obter uma representacao de triangulacoes bidimensionais compacta.
5.1 A Estrutura
Como discutido na Secao 2.6, constatou-se que mesmo representacoes compactas
possuem uma redundancia consideravel no armazenamento da topologia. No caso
de estruturas de dados baseadas em vertices, arestas e faces sao representadas im-
plicitamente multiplas vezes. Considere uma triangulacao G representada por uma
listas de incidencias simples, onde cada vertice guarda referencias para todos os seus
vertices vizinhos. E fato entao que toda face e representada tres vezes, uma contri-
buicao devido a cada um de seus vertices. Para as arestas, a situacao e ainda pior,
pois agora quatro vertices representarao a mesma informacao, suas extremidades e
54
dois vertices das duas faces adjacentes. Buscaremos reduzir esta redundancia por
meio do controle das referencias recıprocas entre vertices adjacentes.
A estrutura proposta e capaz de representar grafos maximais planares, apesar de
nao ser difıcil estende-la para o caso de grafos planares arbitrarios. Para unificar a
representacao das faces, mantem-se um vertice fictıcio, denominado vertice infinito, o
qual supostamente esta conectado a todos os vertices no contorno da triangulacao.
Isto faz com que a face ilimitada do grafo seja subdividida em faces infinitas de
tamanho constante e igual a tres.
Procederemos agora a descricao da estrutura. Para tanto, considere uma tri-
angulacao G arbitraria e um transversal de triangulos por vertice X de G. Faca
X = V \ X. O elementos de X sao denominados guardas, enquanto que os de
X sao os guardados. Um vertice que ainda nao foi inserido em G e denominado
nao-guardado ou descoberto.
Para cada vertice do tipo guarda v ∈ X, armazenamos referencias a todos os
vertices do conjunto N(v). Por outro lado, cada vertice guardado v ∈ X apontara
para todo vertice u ∈ X tal que v ∈ N(u). Como nem sempre existem transversais
independentes, observe que e possıvel existir guardas com referencias recıprocas.
Este fato estara associado a quantidade de redundancia presente em nossa estrutura.
A Figura 5.1 apresenta uma ilustracao da utilizacao de nossa estrutura. Existem
quatro vertices no transversal, incluindo o vertice infinito. A partir da Figura 5.1d,
pode-se concluir que foram poupadas 8 referencias entre vertices guardados.
Em uma triangulacao, o numero de faces compartilhadas entre dois vertices
adjacentes e igual a 2. Esta informacao sera util para o algoritmo de remocao de
faces, ao remover guardas da vizinhanca de vertices guardados. Sendo assim, apenas
os vertices guardados precisam armazenar este valor para cada um de seus guardas.
Teorema 5.1. Uma triangulacao G com n vertices pode ser representada utilizando
no maximo 5n− 10 referencias.
Demonstracao. Seja X um conjunto transversal de triangulos para G e faca X =
V \X. Defina o grau de um vertice guardado v, denotado por deg(v), como sendo o
55
(a) Triangulacao. (b) Vertices guardas e guardados.
∞
∞
∞
(c) Referencias de vertices guardas.
∞ ∞
∞
∞
(d) Referencias de vertices guardados.
Figura 5.1: Esquema de representacao de uma triangulacao com 9 vertices, in-
cluindo o vertice infinito, utilizando a estrutura de dados baseada em transversais
de triangulos. Vertices guardas e guardados sao indicados por cırculos e quadrados,
respectivamente.
numero de guardas adjacentes a v. O numero total de referencias k utilizadas pela
estrutura obedece a seguinte desigualdade:
k =∑v∈X
deg(v) +∑v∈X
deg(v) = 2|E| −∑v∈X
(deg(v)− deg(v)
) ≤ 2|E|. (5.1)
O Corolario 2.1 assegura a existencia de um transversal X de G tal que |X| ≤bn/2c, o qual e calculado pelo algoritmo descrito na Secao 3.3.1. Sejam G∗ o grafo
dual de G e M∗ um emparelhamento perfeito de G∗. A cardinalidade do conjunto
M∗ e |F (G)|/2 = n − 2. Seja G′ o subgrafo de G induzido pela remocao de cada
aresta e ∈ E tal que e∗ ∈ M∗, onde e∗ e a aresta dual a e. Como todo vertice de
G′ possui grau par, entao G′ possui uma 2-coloracao propria. Seja {V1, V2}, com
56
|V1| ≤ |V2|, a particao induzida pela 2-coloracao de G′. Observe que a cada par de
vertices de mesma cor em G′ corresponde uma aresta de G que foi removida. Entao
foram removidas ≤ (n − 2)/2 arestas entre pares de vertices de V1 e ≥ (n − 2)/2
arestas entre pares de vertices de V2. Fazendo X = V1 e X = V2, temos que∑v∈X
(deg(v)− deg(v)
) ≥ n− 2. Logo, k ≥ 2|E| − (n− 2) = 5n− 10.
Observe que se X = V , entao a estrutura e identica a uma lista de adjacencias.
Caso contrario, desde que listas de adjacencias necessitam de aproximadamente
6n referencias, comparativamente, o uso da presente estrutura implicaria em uma
reducao em torno de 16% do espaco em memoria consumido, seja considerando
referencias de tamanho constante ou variavel.
5.1.1 Interface
Observe que os vertices, tanto os guardas quanto os guardados, serao os unicos obje-
tos representados explicitamente. Cada vertice e acessado por um rotulo exclusivo.
Se i e o rotulo de um vertice em V , entao escrevemos vi para denotar este vertice.
Este rotulo pode ser de tamanho fixo (32 ou 64 bits) ou variavel, como por exemplo
codigos gama [74]. O importante e que o custo de acesso a um vertice permaneca
O(1) ou, ao menos, assintoticamente constante. Os vertices armazenam ainda um
campo para identificar seu tipo.
As faces sao representadas implicitamente por triplas de rotulos de vertices.
Sendo assim, uma face f ∈ F (G) e escrita como (a, b, c), onde a, b e c sao rotulos de
vertices em V (G). Usamos fi, i = 0, 1, 2, para denotar os rotulos de seus vertices.
De modo analogo, uma aresta e ∈ E e representada pelo par (a, b), onde a e b
sao os rotulos dos vertices de suas extremidades. Estes rotulos tambem podem ser
representados por e0 e e1.
Basicamente, a interface da nova estrutura e compreendida por tres funcoes:
neighbor(f, i), insert(f) e remove(f). A funcao neighbor(f, i) e utilizada para per-
correr as adjacencias das faces da triangulacao, enquanto que as demais servem para
atualizar a topologia.
57
Os algoritmos de manipulacao sao similares aos de BLANDFORD et al. [1]. Adi-
cionalmente, agora e necessario gerenciar a criacao e destruicao de vertices segundo
o seu tipo, seja ele guarda ou guardado.
Antes de iniciar a descricao dos algoritmos, e conveniente definir as bijecoes
ccw: {0, 1, 2} → {1, 2, 0} e cw: {0, 1, 2} → {2, 0, 1}, as quais denotam permutacoes
no sentido anti-horario e horario, respectivamente. Se f = (a, b, c) pertence a F ,
entao fccw(0) = b, fccw(1) = c e fccw(2) = a. Do mesmo modo, temos que fcw(0) = c,
fcw(1) = a e fcw(2) = b.
O i-esimo Vizinho
Dada uma face f = (a, b, c) em G, dizemos que seu i-esimo vizinho e a face em F
que compartilha a aresta de f oposta ao seu i-esimo vertice. Portanto, o segundo
vizinho de uma face (a, b, c) ∈ F deve ser uma face (a, c, d) ∈ F , onde d e o rotulo
de algum vertice em V . A funcao neighbor(f, i) realiza esta tarefa como a seguir.
Sejam a′ = fi, b′ = fccw(i) e c′ = fcw(i). Se b′ e c′ forem vertices guardados,
percorre-se a lista de vertices vizinhos de cada guarda de b′ (ou c′) ate encontrar a
aresta (c′, b′). Se a aresta (b′, c′) existir em E, entao deve existir um guarda com
rotulo d em X tal que b′ e c′ pertencam a N(vd). Logo, (c′, b′, d) e a face procurada.
Caso b′ seja um vertice guarda, basta percorrer N(vb′) em busca da aresta (c′, a′).
Denotando por d o antecessor de c′ em N(vb′), entao a face procurada e (c′, b′, d).
Se b′ estiver guardado e c′ for um guarda, procuramos em N(vc′) a ocorrencia da
aresta (a′, b′). O terceiro vertice da face procurada sera justamente o sucessor de b′
em N(vc′).
Insercao
A insercao de uma face f = (a, b, c) em F (G) requer atualizar a lista de vertices
adjacentes de cada vertice de f levando em consideracao seu tipo. Para este fim,
esta estrutura fornece a funcao insert(f), cujo algoritmo e o seguinte.
Para cada i ∈ {0, 1, 2}, faca a′ = fi, b′ = fccw(i) e c′ = fcw(i). Se vb′ e vc′ nao forem
58
guardas, entao va′ deve se tornar um guarda e a aresta (b′, c′) deve ser adicionada a
vizinhanca de va′ . Caso contrario, se va′ ja for do tipo guarda, entao basta adicionar
(b′, c′) a sua vizinhanca.
Quando va′ estiver guardado por algum outro vertice de X, entao, obrigatoria-
mente, um dos vertices associados aos rotulos b′ e c′ deve ser do tipo guarda. Entao,
destes, adicione a vizinhanca de va′ os que forem guardas.
Remocao
A remocao de uma face f = (a, b, c) ∈ F (G) e realizada pela funcao remove(f).
Esta requer que nenhum de seus vertices esteja descoberto, pois isto significaria que
f ainda nao pertence a triangulacao. O algoritmo da remove(f) modificara a lista
de vizinhos de cada vertice de vfi, para i ∈ {0, 1, 2}.
Inicialmente, consideramos todos os vertices guardas de f . Se vfie um guarda,
faca a′ = fi, b′ = fccw(i) e c′ = fcw(i). Entao, remova a aresta (b′, c′) de N(a′).
Neste instante, qualquer vertice ainda nao visitado pela remove(f) devera ser do
tipo guardado. Como comentado anteriormente, cada vertice guardado armazena o
numero de faces compartilhadas com cada um de seus guardas. Entao, ao remover
um guarda, alem de remove-lo de sua vizinhanca, e necessario decrementar este
valor. Somente quando nao houver nenhuma face compartilhada e que um guarda
sera removido de fato.
5.2 Construcao da Triangulacao de Delaunay
O desempenho da estrutura de dados desenvolvida sera avaliado por meio de sua
aplicacao na construcao de triangulacoes de bidimensionais. Dado um conjunto
S de pontos em R2, uma triangulacao de S e uma particao do fecho convexo de
seus pontos em simplexos (faces) com vertices em S. A triangulacao de Delaunay
DT (S) e caracterizada pela propriedade do circuncirculo vazio, a qual afirma que o
circuncirculo de qualquer face de DT (S) nao contem nenhum outro ponto de S em
seu interior. Diz-se que um ponto p esta em conflito com uma face em DT (S) se
59
este pertencer ao circuncirculo desta face. A regiao de conflito do ponto p e definida
como a colecao de todas estas faces. Pode-se demonstrar que esta regiao e sempre
conexa.
Existem diversos algoritmos para a construcao de triangulacoes de Delaunay
em 2D [75–81]. Optamos por implementar um algoritmo de construcao incremen-
tal visto que este possibilitara construir uma triangulacao sem a necessidade de
realocar os vertices guardas e guardados, como sera demonstrado a seguir. Neste
algoritmo, a insercao de um ponto p pode ser dividida em dois passos: localizacao
e atualizacao. O passo de localizacao busca determinar a face f em DT (S) que
contem p utilizando uma caminhada estocastica “com memoria” [82]. Esta cami-
nhada e dita “com memoria” por sempre iniciar de uma face incidente ao vertice
criado anteriormente, e “estocastica” por percorrer as faces usando uma decisao
aleatoria sobre qual direcao tomar baseada em testes de orientacao bidimensionais.
Durante a atualizacao, a regiao de conflito de p e determinada segundo o algoritmo
de Bowyer-Watson, isto e, a propriedade do circuncirculo vazio e verificada para to-
dos os vizinhos de f utilizando uma busca em profundidade. As faces conflitantes sao
removidas, criando uma “cavidade” na triangulacao, e a triangulacao e finalmente
atualizada ao criar novas faces conectando p aos vertices do contorno da cavidade.
Adicionalmente, o passo de atualizacao utilizando a estrutura de dados proposta
requer decidir sobre a criacao de novos guardas. Se nenhum dos vertices perten-
centes ao contorno da cavidade criada for um guarda, entao o vertice induzido pelo
ponto p deve ser um guarda. Alem disso, na atual implementacao, o vertice infinito
e representado apenas implicitamente. Sendo assim, seria impossıvel percorrer di-
retamente sua lista de vertices adjacentes, pois esta lista nao e armazenada. Para
contornar este problema, e necessario manter sempre dois guardas no contorno adja-
centes a cada vertice guardado. Portanto, se o ponto p estiver fora do fecho convexo
da triangulacao de S \ {p}, entao o novo vertice sera do tipo guarda.
Em algoritmos de construcao incremental randomizada, o acesso aleatorio a
memoria RAM pode leva-lo a ter serios problemas de performance. Foi observado
60
que uma implementacao ingenua deste algoritmo pode acarretar em hiperpaginacao
[83]. Isto pode ser remediado com o utilizacao de uma ordem de insercao randomi-
zada enviesada para reduzir a quantidade de aleatoriedade. Basicamente, os pontos
de S sao separados em subconjuntos Si, onde i = 0, 1, . . . , log n. Estes subconjun-
tos sao construıdos na ordem inversa. Cada ponto e atribuıdo a um subconjunto
com probabilidade 1/2. Ao chegar em S0, os pontos restantes sao escolhidos com
probabilidade 1. Foi demonstrado ainda que se os pontos de cada subconjunto Si
forem inseridos segundo uma ordem arbitraria, o custo esperado do algoritmo de
construcao randomizada fica inalterado [83]. A biblioteca CGAL contem uma im-
plementacao de uma ordem enviesada utilizando uma curva de Hilbert para ordenar
os pontos dentro de cada subconjunto Si [84]. Esta implementacao foi recentemente
avaliada tambem em paralelo [85–87]. A partir dos resultados que obtivemos nesta
experiencia, optamos por emprega-la em na presente implementacao.
5.3 Resultados Experimentais
O esquema de representacao baseado em vertices proposto foi implementado em
C++, com o auxılio das bibliotecas STL, Boost e CGAL. Como nao estamos in-
teressados na compressao dos rotulos dos vertices em si, estes foram represen-
tados por numeros inteiros simples de 32 bits (int, em C++). Sendo assim, a
lista de vizinhos de um vertice guarda Guard neighbors range foi implementada
como std::list<Guard vertex label>, com Guard vertex label igual a int. No
caso dos vertices guardados, utilizamos std::list<Guarded vertex label>, onde
Guarded vertex label e como a seguir:
struct Guarded_vertex_label {
char counter : 2;
int label;
};
61
A manipulacao destas listas foi uniformizada com a utilizacao da classe
boost::variant, a qual e uma especie de union capaz de armazenar objetos de
tipos heterogeneos. Basicamente, cada vertice contem uma variavel privada que ar-
mazena a lista de seus vizinhos declarada como do tipo boost::variant< Guard -
neighbors range, Guarded neighbors range >, onde Guarded neighbors range
e definido como std::list<Guarded vertex label>.
Cada vertice tambem carreia consigo uma variavel para identificar o seu tipo.
Para tanto, definiu-se a estrutura:
struct Vertex_type {
char _type : 2;
}
Os vertices foram implementados sob a forma de uma classe denominada
Triangulation ds vertex base 2, cujo conteudo pode ser resumido como abaixo:
class Triangulation_ds_vertex_base_2 {
...
private:
boost::variant< Guard_neighbors_range,
Guarded_neighbors_range > _neighbors;
Vertex_type _type;
Point _p;
};
Os codigos foram compilados utilizando o compilador g++, com as seguintes
opcoes de otimizacao habilitadas: -O3, -DNDEBUG e -frounding-math. Todos os
testes foram realizados em um computador com processador Intel Core i7 840QM
64-bit com 4GB de RAM DDR3 de 1333 MHz. Mais detalhes sobre o aparato
experimental podem ser obtidos na Secao 3.4.
Utilizamos quatro distribuicoes diferentes de pontos no plano com tamanhos
entre 1 e 8 milhoes (ver Secao 3.4 para melhores descricoes sobre estas distribuicoes).
62
A Figura 5.2 ilustra as triangulacoes construıdas pela nossa implementacao para
cada uma destas distribuicoes, com 10 mil vertices.
Faremos comparacoes com uma implementacao do esquema de BLANDFORD
et al. [1], sem considerar a compressao dos rotulos, visto esta ter servido de base
para a implementacao da solucao proposta na presente tese. Para fins de referencia,
usaremos ainda a implementacao de algoritmo de triangulacao de Delaunay fornecida
pela CGAL [88, 89]. Isto possibilitara avaliar o impacto na performance devido ao
nıvel de indirecao introduzido.
As Figuras 5.3a 5.4a 5.5a 5.6a contem os tempos de processamento gastos por
cada uma das tres implementacoes consideradas. As representacoes baseadas em
vertices foram cerca de 10 vezes mais lentas do que a da CGAL. Pode-se observar
ainda que a estrutura baseada em transversais de triangulos foi cerca de 18% mais
rapida do que a implementacao sem compressao de BLANDFORD et al. [1], em
todos os conjuntos de pontos. Isto deve estar relacionado com a diminuicao do
numero de referencias empregadas pela nossa estrutura, como mostram as Figuras
5.3b 5.4b 5.5b 5.6b.
Ainda em termos do numero de referencias, foi possıvel reduzir em media 12%
e 59% em relacao a estrutura descomprimida de BLANDFORD et al. [1] e a do
CGAL, respectivamente.
A taxa de vertices no transversal para a triangulacao final ficou sempre em torno
de 58%. Para todos os conjuntos de pontos, o numero de referencias armazenadas
pelos guardas representa aproximadamente 67.5% do total, enquanto que os 32.5%
restantes sao armazenadas em vertices guardados.
Vale ressaltar que, como descrito anteriormente, a vizinhanca de cada vertice foi
armazenada com o auxılio de listas duplamente encadeadas (std::list). Isto acar-
reta em uma sobrecarga em memoria, pois cada elemento da lista, na verdade, arma-
zena o rotulo de um vertice mais os enderecos do proximo e do anterior. Este onus
foi provavelmente o responsavel pela diferenca acentuada dos tempos de execucao
entre nossa implementacao e a do CGAL.
63
(a) Uniforme em quadrado. (b) Uniforme em disco.
(c) Normal. (d) Normal ponderada.
Figura 5.2: Ilustracao das triangulacoes calculadas pela implementacao da estrutura
proposta para quatro tipos diferentes de distribuicoes de pontos no plano.
64
0
20
40
60
80
100
120
1 M 2 M 4 M 6 M 8 M
Tem
po d
e C
PU
(se
gund
os)
Número de Pontos
PropostaBlandford et al
CGAL
(a)
20 M
40 M
60 M
80 M
100 M
120 M
1 M 2 M 4 M 6 M 8 M
Núm
ero
de R
efer
ênci
as
Número de Pontos
PropostaBlandford et al
CGAL
(b)
Figura 5.3: (a) Tempo de CPU gasto por cada implementacao na construcao de
triangulacoes de Delaunay e (b) numero de referencias representadas para o conjunto
de pontos distribuıdos uniformemente no interior de um quadrado unitario.
65
0
20
40
60
80
100
120
1 M 2 M 4 M 6 M 8 M
Tem
po d
e C
PU
(se
gund
os)
Número de Pontos
PropostaBlandford et al
CGAL
(a)
20 M
40 M
60 M
80 M
100 M
120 M
1 M 2 M 4 M 6 M 8 M
Núm
ero
de R
efer
ênci
as
Número de Pontos
PropostaBlandford et al
CGAL
(b)
Figura 5.4: (a) Tempo de CPU gasto por cada implementacao na construcao de
triangulacoes de Delaunay e (b) numero de referencias representadas para o conjunto
de pontos distribuıdos uniformemente no interior de um cırculo unitario.
66
0
20
40
60
80
100
120
1 M 2 M 4 M 6 M 8 M
Tem
po d
e C
PU
(se
gund
os)
Número de Pontos
PropostaBlandford et al
CGAL
(a)
20 M
40 M
60 M
80 M
100 M
120 M
1 M 2 M 4 M 6 M 8 M
Núm
ero
de R
efer
ênci
as
Número de Pontos
PropostaBlandford et al
CGAL
(b)
Figura 5.5: (a) Tempo de CPU gasto por cada implementacao na construcao de
triangulacoes de Delaunay e (b) numero de referencias representadas para o conjunto
de pontos normalmente distribuıdos no interior de um quadrado unitario.
67
0
20
40
60
80
100
120
1 M 2 M 4 M 6 M 8 M
Tem
po d
e C
PU
(se
gund
os)
Número de Pontos
PropostaBlandford et al
CGAL
(a)
20 M
40 M
60 M
80 M
100 M
120 M
1 M 2 M 4 M 6 M 8 M
Núm
ero
de R
efer
ênci
as
Número de Pontos
PropostaBlandford et al
CGAL
(b)
Figura 5.6: (a) Tempo de CPU gasto por cada implementacao na construcao de
triangulacoes de Delaunay e (b) numero de referencias representadas para o conjunto
de pontos distribuıdos segundo a distribuicao normal ponderada.
68
Capıtulo 6
Consideracoes Finais
Neste trabalho, foram abordadas questoes teoricas sobre conjuntos transversais de
triangulos e suas aplicacoes na engenharia, sob a forma de uma representacao de
triangulacoes bidimensionais. Do ponto de vista teorico, os resultados obtidos de-
monstraram a NP-completude de se calcular conjuntos transversais de cardinalidade
mınima mesmo em grafos maximais planares de grau limitado 5. Estes resultados
promoveram tambem a comprovacao de que o problema de posicionamento de guar-
das em terrenos poliedricos, sejam eles guardas fixos ou moveis, e NP-difıcil. Alem
disso, foi observado que nao e difıcil obter um algoritmo capaz de calcular transver-
sais de triangulos por vertice de tamanho otimo no pior caso, ou um pouco acima
do valor otimo, mas gastando menos tempo.
Em se tratando da representacao de triangulacoes desenvolvida, mesmo com um
conjunto transversal de cardinalidade em media 8% acima do valor otimo de bn/2c,foi possıvel reduzir a quantidade de referencias recıprocas. Esta reducao torna viavel
o emprego desta estrutura em situacoes praticas, desde que aliada a esquemas de
compressao de rotulos mais agressivos, tais como os codigos de diferencas. Neste
caso, a proximidade geometrica entre os pontos, fornecida via uma ordecao espacial
como a associada a uma curva de Hilbert, pode ser utilizada para produzir diferencas
mais compactas entre os rotulos de vertices vizinhos. Isto seria uma alternativa a
metodos baseados em propriedades de separabilidades de grafos [1].
Por fim, seria interessante investigar a possibilidade de realocar vertices guardas
69
e guardados durante a construcao da triangulacao de modo a assegurar o tamanho
do conjunto transversal sempre abaixo de bn/2c. Isto podera ser aplicado na manu-
tencao de triangulacoes de Delaunay cujos vertices movem ao longo do tempo, como
em simulacoes utilizando metodos de elementos finitos com malhas adaptativas.
70
Referencias Bibliograficas
[1] BLANDFORD, D., BLELLOCH, G., CARDOZE, D., et al. “Compact represen-
tations of simplicial meshes in two and three dimensions”, International
Journal of Computational Geometry & Applications, v. 15, n. 1, pp. 3–24,
2005. doi: 10.1142/S0218195905001580.
[2] ROSSIGNAC, J. “Edgebreaker: connectivity compression for triangle meshes”,
Visualization and Computer Graphics, IEEE Transactions on, v. 5, n. 1,
pp. 47 –61, 1999. doi: 10.1109/2945.764870.
[3] ALEARDI, L. C., DEVILLERS, O., SCHAEFFER, G. “Optimal succinct repre-
sentations of planar maps”. In: SCG ’06: Proceedings of the 22nd Annual
Symposium on Computational Geometry, pp. 309–318, New York, NY,
USA, 2006. ACM. doi: 10.1145/1137856.1137902.
[4] ALEARDI, L. C., FUSY, E., LEWINER, T. “Optimal encoding of triangu-
lar and quadrangular meshes with fixed topology”. In: Proceedings of
the 22nd Annual Canadian Conference on Computational Geometry, pp.
95–98, Manitoba, Canada, 2010. Disponıvel em: <http://cccg.ca/
proceedings/2010/paper27.pdf>.
[5] ISENBURG, M., LINDSTROM, P. “Streaming meshes”. In: Visualiza-
tion, 2005. VIS 05. IEEE, pp. 231 – 238, 2005. doi: 10.1109/VI-
SUAL.2005.1532800.
[6] WU, J., KOBBELT, L. “A Stream Algorithm for the Decimation of Massive
Meshes”. In: Graphics Interface, pp. 185–192, 2003.
[7] LINDSTROM, P. “Out-of-core construction and visualization of multireso-
lution surfaces”. In: Proceedings of the 2003 symposium on Interac-
tive 3D graphics, pp. 93–102, New York, NY, USA, 2003. ACM. doi:
10.1145/641480.641500.
[8] KEELER, K., WESTBROOK, J. “Short encodings of planar graphs and maps”,
Discrete Appl. Math., v. 58, n. 3, pp. 239–252, 1995. doi: 10.1016/0166-
218X(93)E0150-W.
71
[9] TURAN, G. “On the succinct representation of graphs”, Discrete Applied Mathe-
matics, v. 8, n. 3, pp. 289 – 294, 1984. doi: 10.1016/0166-218X(84)90126-4.
[10] GUMHOLD, S., STRASSER, W. “Real time compression of triangle mesh
connectivity”. In: Proceedings of the 25th annual conference on Computer
graphics and interactive techniques, pp. 133–140, New York, NY, USA,
1998. ACM. doi: 10.1145/280814.280836.
[11] ALLIEZ, P., DESBRUN, M. “Progressive compression for lossless transmission
of triangle meshes”. In: Proceedings of the 28th annual conference on
Computer graphics and interactive techniques, pp. 195–202, New York,
NY, USA, 2001. ACM. doi: 10.1145/383259.383281.
[12] TOUMA, C., GOTSMAN, C. “Triangle Mesh Compression”. In: Proceedings
of the Graphics Interface 1998 Conference, pp. 26–34, Vancouver, BC,
Canada, 1998.
[13] GANDOIN, P.-M., DEVILLERS, O. “Progressive lossless compression of arbi-
trary simplicial complexes”, ACM Trans. Graph., v. 21, n. 3, pp. 372–379,
July 2002. doi: 10.1145/566654.566591.
[14] POULALHON, D., SCHAEFFER, G. “Optimal Coding and Sampling of
Triangulations”, Algorithmica, v. 46, n. 3, pp. 505–527, 2006. doi:
10.1007/s00453-006-0114-8.
[15] CHOU, P. H., MENG, T. H. “Vertex Data Compression through Vector Quan-
tization”, IEEE Transactions on Visualization and Computer Graphics,
v. 8, n. 4, pp. 373–382, 2002. doi: 10.1109/TVCG.2002.1044522.
[16] LEE, E.-S., KO, H.-S. “Vertex Data Compression for Triangular Meshes”.
In: Proceedings of the 8th Pacific Conference on Computer Graphics and
Applications, pp. 225–234, Washington, DC, USA, 2000. IEEE Computer
Society.
[17] DEERING, M. “Geometry compression”. In: Proceedings of the 22nd annual
conference on Computer graphics and interactive techniques, pp. 13–20,
New York, NY, USA, 1995. ACM. doi: 10.1145/218380.218391.
[18] BAJAJ, C. L., PASCUCCI, V., ZHUANG, G. “Single Resolution Compression
of Arbitrary Triangular Meshes with Properties”. In: Proceedings of the
Conference on Data Compression, pp. 247–256, Washington, DC, USA,
1999. IEEE Computer Society.
72
[19] TAUBIN, G., ROSSIGNAC, J. “Geometric compression through topologi-
cal surgery”, ACM Trans. Graph., v. 17, n. 2, pp. 84–115, 1998. doi:
10.1145/274363.274365.
[20] CHOW, M. M. “Optimized geometry compression for real-time rendering”. In:
Proceedings of the 8th conference on Visualization ’97, pp. 347–354, Los
Alamitos, CA, USA, 1997. IEEE Computer Society Press.
[21] COLE, R., SHARIR, M. “Visibility Problems for Polyhedral Terrains”, Journal
of Symbolic Computation, v. 7, n. 1, pp. 11 – 30, 1989. doi: 10.1016/S0747-
7171(89)80003-3.
[22] BOSE, P., KIRKPATRICK, D., LI, Z. “Worst-case-optimal Algorithms for
Guarding Planar Graphs and Polyhedral Surfaces”, Computational Ge-
ometry: Theory and Applications, v. 26, pp. 209–219, 2003. doi:
10.1016/S0925-7721(03)00027-0.
[23] BRUGMANN, D., KOMUSIEWICZ, C., MOSER, H. “On Generating Triangle-
Free Graphs”, Electronic Notes in Discrete Mathematics, v. 32, pp. 51 –
58, 2009. doi: 10.1016/j.endm.2009.02.008.
[24] ZHU, B. Computational geometry in two and a half dimensions. Tese de Dou-
torado, McGill University, Montreal, Canada, 1994.
[25] “Cgal: Computational Geometry Algorithms Library”. Disponıvel em:
<http://www.cgal.org/>.
[26] BATISTA, V. H. F., RIBEIRO, F. L. B., PROTTI, F. “On the complexity of the
edge guarding problem”. In: Proceedings of the 26th European Workshop
on Computational Geometry (EuroCG’10), Dortmund, Germany, March
2010.
[27] KARP, R. “Reducibility among combinatorial problems”. In: Miller, R., That-
cher, J. (Eds.), Complexity of Computer Computations, Plenum Press, pp.
85–103, New York, NY, 1972.
[28] STOCKMEYER, L. “Planar 3-colorability is polynomial complete”, SIGACT
News, v. 5, pp. 19–25, July 1973. doi: 10.1145/1008293.1008294.
[29] KEMPE, A. B. “On the Geographical Problem of the Four Colours”, American
Journal of Mathematics, v. 2, n. 3, pp. 193–200, 1879.
[30] HEAWOOD, P. J. “On the four-color map theorem”, Quarterly J. Pure &
Applied Math, v. 29, pp. 270–285, 1898.
73
[31] STEINBERG, R. “The State of the Three Color Problem”. In: John Gimbel,
J. W. K., Quintas, L. V. (Eds.), Quo Vadis, Graph Theory? - A Source
Book for Challenges and Directions, v. 55, Annals of Discrete Mathema-
tics, Elsevier, pp. 211 – 248, Amsterdam, NL, 1993. doi: 10.1016/S0167-
5060(08)70391-1.
[32] APPEL, K., HAKEN, W., KOCH, J. “Every planar map is four colorable. II:
Reducibility.” Ill. J. Math., v. 21, pp. 491–567, 1977.
[33] ROBERTSON, N., SANDERS, D., SEYMOUR, P., et al. “The Four-Colour
Theorem”, Journal of Combinatorial Theory, Series B, v. 70, n. 1, pp. 2
– 44, 1997. doi: 10.1006/jctb.1997.1750.
[34] MOHAR, B., SKREKOVSKI, R. “The Grotzsch Theorem for the hypergraph
of maximal cliques”, Electron. J. Combin, v. 6, pp. 26–13, 1999.
[35] ALON, N., BERKE, R., BUCHIN, K., et al. “Polychromatic Colorings of Plane
Graphs”, Discrete and Computational Geometry, v. 42, n. 3, pp. 421–442,
2009. doi: 10.1007/s00454-009-9171-5.
[36] PETERSEN, J. “Die Theorie der regularen graphs”, Acta Mathematica, v. 15,
pp. 193–220, 1891. doi: 10.1007/BF02392606.
[37] BONDY, J. A., MURTY, U. S. R. Graph Theory. N. 244, Graduate Texts in
Mathematics. Berlin Heidelberg, Springer-Verlag, 2008.
[38] EDMONDS, J. “Paths, Trees, and Flowers”, Canad. J. Math., v. 17, pp. 449–
467, 1965.
[39] MICALI, S., VAZIRANI, V. V. “An O(√|v|·|E|) algorithm for finding maxi-
mum matching in general graphs”. In: Proceedings of the Annual IEEE
Symposium on Foundations of Computer Science, pp. 17–27, Los Alami-
tos, CA, USA, 1980. doi: 10.1109/SFCS.1980.12.
[40] BLUM, N. “A New Approach to Maximum Matching in General Graphs”.
In: Proceedings of the 17th International Colloquium on Automata, Lan-
guages and Programming (ICALP ’90), pp. 586–597, London, UK, 1990.
Springer-Verlag.
[41] GABOW, H. N., TARJAN, R. E. “Faster scaling algorithms for general graph
matching problems”, J. ACM, v. 38, pp. 815–853, October 1991. doi:
10.1145/115234.115366.
74
[42] BIEDL, T. C., BOSE, P., DEMAINE, E. D., et al. “Efficient Algorithms for
Petersen’s Matching Theorem”, Journal of Algorithms, v. 38, pp. 110–134,
2001.
[43] COOK, S. A. “The complexity of theorem-proving procedures”. In: STOC
’71: Proceedings of the third annual ACM symposium on Theory of
computing, pp. 151–158, New York, NY, USA, 1971. ACM. doi:
10.1145/800157.805047.
[44] LICHTENSTEIN, D. “Planar Formulae and Their Uses”, SIAM Journal on
Computing, v. 11, n. 2, 1982. doi: 10.1137/0211025.
[45] TOVEY, C. “A simplified NP-complete satisfiability problem”, Discrete Ap-
plied Mathematics, v. 8, n. 1, pp. 85–89, 1984. doi: 10.1016/0166-
218X(84)90081-7.
[46] HALL, P. “On Representatives of Subsets”, Journal of the London Mathema-
tical Society, v. 10, pp. 26–30, 1935. doi: 10.1112/jlms/s1-10.37.26.
[47] YANNAKAKIS, M. “Node-and edge-deletion NP-complete problems”. In:
STOC ’78: Proceedings of the tenth annual ACM symposium on The-
ory of computing, pp. 253–264, New York, NY, USA, 1978. ACM. doi:
10.1145/800133.804355.
[48] GAREY, M. R., JOHNSON, D. S. Computers and Intractability: A Guide to
the Theory of NP-Completeness. New York, NY, USA, W. H. Freeman &
Co., 1979.
[49] GROSHAUS, M., HELL, P., KLEIN, S., et al. “Cycle transversals in bounded
degree graphs”, Electronic Notes in Discrete Mathematics, v. 35, pp. 189
– 195, 2009.
[50] CHVATAL, V. “A combinatorial theorem in plane geometry”, J. Comb. Theory
Ser. B, v. 18, pp. 39–41, 1975. doi: 10.1016/0095-8956(75)90061-1.
[51] FISK, S. “A short proof of Chvatal’s watchman theorem”, J. Combin. Theory
Ser. B, v. 24, pp. 374, 1978. doi: 10.1016/0095-8956(78)90059-X.
[52] O’ROURKE, J. Art gallery theorems and algorithms. New York, NY, USA,
Oxford University Press, Inc., 1987.
[53] SHERMER, T. “Recent results in art galleries”, Proceedings of the IEEE, v. 80,
n. 9, pp. 1384 –1399, 1992. doi: 10.1109/5.163407.
75
[54] URRUTIA, J. “Art Gallery and Illumination Problems”. In: Sack, J.-R., Urru-
tia, J. (Eds.), Handbook of Computational Geometry, North-Holland, pp.
973 – 1027, Amsterdam, 2000. doi: 10.1016/B978-044482537-7/50023-1.
[55] BOSE, P., SHERMER, T., TOUSSAINT, G., et al. “Guarding Polyhedral Ter-
rains”, Computational Geometry: Theory and Applications, v. 7, pp. 173–
185, 1997. doi: 10.1016/0925-7721(95)00034-8.
[56] EVERETT, H., RIVERA-CAMPO, E. “Edge guarding polyhedral terrains”,
Computational Geometry, v. 7, n. 3, pp. 201–203, 1997.
[57] TUTTE, W. “A Census of Planar Triangulations”, Canadian Journal of Mathe-
matics, v. 14, pp. 21–38, 1962.
[58] SHAMOS, M. I. Computational Geometry. Tese de Doutorado, Yale University,
1978.
[59] JACOBSON, G. “Space-efficient static trees and graphs”. In: Proceedings of
the 30th Annual Symposium on Foundations of Computer Science, pp.
549–554, Research Triangle Park, 1989. doi: 10.1109/SFCS.1989.63533.
[60] MUNRO, J. I., RAMAN, V. “Succinct Representation of Balanced Parentheses
and Static Trees”, SIAM J. Comput., v. 31, n. 3, pp. 762–776, 2001. ISSN:
0097-5397. doi: 10.1137/S0097539799364092.
[61] POULALHON, D., SCHAEFFER, G. “Optimal Coding and Sampling of
Triangulations”, Algorithmica, v. 46, n. 3, pp. 505–527, 2006. doi:
10.1007/s00453-006-0114-8.
[62] MEBARKI, A. Implantation de structures de donnees compactes pour les trian-
gulations. Tese de Doutorado, Universite de Nice-Sophia Antipolis, 2008.
[63] BAUMGART, B. G. Winged edge polyhedron representation. Research report,
Stanford University, Stanford, CA, USA, 1972.
[64] PREPARATA, F. P., SHAMOS, M. I. Computational Geometry: An Introduc-
tion. New York, NY, USA, Springer-Verlag, 1985.
[65] GUIBAS, L., STOLFI, J. “Primitives for the manipulation of general subdivi-
sions and the computation of Voronoi”, ACM Trans. Graph., v. 4, n. 2,
pp. 74–123, 1985. doi: 10.1145/282918.282923.
[66] CAMPAGNA, S., KOBBELT, L., SEIDEL, H.-P. “Directed Edges – A Scalable
Representation for Triangle Meshes”, Journal of Graphics Tools, v. 3, n. 4,
pp. 1–12, 1998.
76
[67] CLINE, A., RENKA, R. “A storage-efficient method for construction of a
Thiessen triangulation.” Rocky Mt. J. Math., v. 14, pp. 119–139, 1984.
doi: 10.1216/RMJ-1984-14-1-119.
[68] KALLMANN, M., THALMANN, D. “Star-vertices: a compact representation
for planar meshes with adjacency information”, Journal of Graphics Tools,
v. 6, n. 1, pp. 7–18, 2001.
[69] GHOSH, S. “Approximation Algorithms for Art Gallery Problems in Polygons
and Terrains”. In: Proceedings of the Workshop on Algorithms and Com-
putation (WALCOM 2010), v. 5942, pp. 21–34, 2010. doi: 10.1007/978-
3-642-11440-3 3.
[70] ROBERTSON, N., SANDERS, D. P., SEYMOUR, P., et al. “Efficiently four-
coloring planar graphs”. In: STOC ’96: Proceedings of the Twenty-eighth
Annual ACM Symposium on Theory of computing, pp. 571–575, New
York, NY, USA, 1996. ACM Press. doi: 10.1145/237814.238005.
[71] CHIBA, N., NISHIZEKI, T., SAITO, N. “A linear 5-coloring algorithm of
planar graphs”, Journal of Algorithms, v. 2, n. 4, pp. 317 – 327, 1981.
doi: 10.1016/0196-6774(81)90031-6.
[72] “Boost C++ Libraries”. Disponıvel em: <http://www.boost.org/>.
[73] “LEDA: Library of Efficient Data types and Algorithms”. Disponıvel em:
<http://www.algorithmic-solutions.info/>.
[74] ELIAS, P. “Universal codeword sets and representations of the integers”, IEEE
Transactions on Information Theory, v. 21, n. 2, pp. 194 – 203, 1975. doi:
10.1109/TIT.1975.1055349.
[75] LAWSON, C. L. “Software for C1 Surface Interpolation”. In: Mathematical
Software III, pp. 161–194. Academic Press, 1977.
[76] BOWYER, A. “Computing Dirichlet Tessellations”, The Computer Journal,
v. 24, n. 2, pp. 162–166, 1981.
[77] WATSON, D. F. “Computing the n–Dimensional Delaunay Tessellation with
Application to Voronoı Polytopes”, The Computer Journal, v. 24, n. 2,
pp. 167–172, 1981.
[78] FORTUNE, S. “A sweepline algorithm for Voronoi diagrams”, Algorithmica,
v. 2, pp. 153–174, 1987. doi: 10.1007/BF01840357.
77
[79] GUIBAS, L., STOLFI, J. “Primitives for the manipulation of general subdivi-
sions and the computation of Voronoi”, ACM Trans. Graph., v. 4, n. 2,
pp. 74–123, 1985. doi: 10.1145/282918.282923.
[80] DWYER, R. “A faster divide-and-conquer algorithm for constructing delau-
nay triangulations”, Algorithmica, v. 2, n. 1, pp. 137–151, 1987. doi:
10.1007/BF01840356.
[81] LEE, D. T., SCHACHTER, B. J. “Two algorithms for constructing a Delaunay
triangulation”, International Journal of Parallel Programming, v. 9, n. 3,
pp. 219–242, 1980. doi: 10.1007/BF00977785.
[82] DEVILLERS, O., PION, S., TEILLAUD, M. “Walking in a Triangulation”,
International Journal of Foundations of Computer Science, v. 13, n. 2,
pp. 181–199, 2002.
[83] AMENTA, N., CHOI, S., ROTE, G. “Incremental constructions con BRIO”.
In: Proceedings of the nineteenth annual symposium on Computational
geometry, SCG ’03, pp. 211–219, New York, NY, USA, 2003. ACM. doi:
10.1145/777792.777824.
[84] DELAGE, C. “Spatial Sorting”. In: CGAL User and Reference Ma-
nual, 3.7 ed., CGAL Editorial Board, 2010. Disponıvel em:
<http://www.cgal.org/Manual/3.7/doc_html/cgal_manual/
packages.html#Pkg:SpatialSorting>.
[85] BATISTA, V. H. F., MILLMAN, D. L., PION, S., et al. Parallel Geometric
Algorithms for Multi-Core Computers. Research Report RR-6749, INRIA,
2008. Disponıvel em: <http://hal.inria.fr/inria-00343804/PDF/
RR-6749.pdf>.
[86] BATISTA, V. H. F., MILLMAN, D. L., PION, S., et al. “Parallel geometric
algorithms for multi-core computers”. In: Proceedings of the 25th annual
symposium on Computational geometry (SoCG ’09), pp. 217–226, New
York, NY, USA, 2009. ACM. doi: 10.1145/1542362.1542404.
[87] BATISTA, V. H. F., MILLMAN, D. L., PION, S., et al. “Parallel geometric
algorithms for multi-core computers”, Computational Geometry, v. 43,
n. 8, pp. 663 – 677, 2010. doi: 10.1016/j.comgeo.2010.04.008. Special Issue
on the 25th Annual Symposium on Computational Geometry (SoCG ’09).
[88] YVINEC, M. “2D Triangulations”. In: CGAL User and Refe-
rence Manual, 3.7 ed., CGAL Editorial Board, 2010. Dis-
78
ponıvel em: <http://www.cgal.org/Manual/3.7/doc_html/cgal_
manual/packages.html#Pkg:Triangulation2>.
[89] PION, S., YVINEC, M. “2D Triangulation Data Structure”. In: CGAL
User and Reference Manual, 3.7 ed., CGAL Editorial Board, 2010.
Disponıvel em: <http://www.cgal.org/Manual/3.7/doc_html/cgal_
manual/packages.html#Pkg:TDS2>.
79