Triangulating a Simple Polygon in Linear Time

Bernard Chazelle

26 de janeiro de 2012

Esta é uma tradução do artigo de Chazelle, feito com vistasao estudo pessoal do tradutor, num esforço de divulgação dosresultados apresentados.

1

2

Resumo. Fornecemos um algoritmo determinísticopara a triangulação de um polígono simples em tempolinear. A estratégia básica é construir uma aproximaçãogrosseira de uma triangulação em uma etapa bottom-up e então usar a informação calculada nesse percursopara refinar a triangulação em uma fase top-down. Asprincipais ferramentas usadas são o polygon-cutting the-orem, que nos fornece um esquema de balanceamento,e o planar separator theorem, cujo papel é essencial nadescoberta de novas diagonais. Apenas estruturas de da-dos elementares são necessárias. Mencionamos algumasaplicações de nosso algoritmo.

Capítulo 1

Introduction

A triangulação de um polígono simples1 tem sido um dos mais des-tacados problemas na geometria computacional em duas dimensões.É uma primitiva básica em computação gráfica e, em geral, pareceser a etapa de pré-processamento natural para a maior parte dasoperações não-triviais em polígonos simples [?, ?]. Lembramos quetriangular um polígono é subdividi-lo em triângulos sem adicionarnovos vértices. Apesar da aparente simplicidade, contudo, o pro-blema da triangulação permaneceu obscuro. Em 1978 Garey etal. [?] forneceram um algoritmo de tempo O(n log n) para triangu-lar um n-ágono simples. Apesar da crença bem difundida de quetriangular deveria ser mais fácil que ordenar, nenhuma prova foiencontrada até 1986, quando Tarjan e Van Wyk [?] encontraramum algoritmo de tempo O(n log log n). Seguindo essa descoberta,Clarkson et al. [?] descobriram o algoritmo Las Vegas, recentementesimplificado por Seidel [?], de tempo esperado O(n log ∗n). Em1989 Kirkpatrick et al. [?] forneceram um novo, e conceitualmentemais simples algoritmo de tempo O(n log log n), e também deri-

1Nota: arestas de um polígono simples intersectam exatamente duas outrasarestas, (somente) em vértices do polígono.

3

4 CAPÍTULO 1. INTRODUCTION

varam um limitante O(n log ∗n) para o caso em que os vérticespossuem coordenadas inteiras limitadas polinomialmente. Outrosresultados do problema da triangulação incluem algoritmos linearesou quasi-lineares para classes restritas de polígonos [?, ?, ?, ?].

Nosso principal resultado e um algoritmo determinístico e linearno tempo para triangulação de um polígono simples. O algoritmo éelementar no sentido de não requerer o uso de qualquer estruturade dados complexa; em particular, não faz uso de dynamic searchtrees, finger trees, ou estruturas para localização de pontos (point-location).

O que faz a rápida triangulação de polígonos um problema difícilé a inadequação de abordagens puramente top-down ou bottom-up.Proceder top-down é olhar o polígono todo e inferir a informaçãoglobas diretamente. Podemos usar o polygon-cutting theorem [?] quediz que o polígono pode ser cortado por uma diagonal em pedaços detamanho aproximadamente igual. O dilema imediato é que, para co-meço de conversa, encontrar al diagonal parece ser tão difícil quantotriangular o poígono todo. Ademais, iríamos precisar encontrar taldiagonal em tempo amortizado sublinear (digamos, limitado porO(n/ log2 n)) para podermos manter vivas nossas esperanças de al-cançar assim um algoritmo de triangulação ótimo. Uma abortagembottom-up, por outro lado, envolve calcular, digamos, triangulaçõesde pedaços da fronteira do polígono. Ela sofre da da falha óbviade que muita informação acaba sendo computada. De fato, diago-nais para pequenos pedaços da fronteira não são garantidamentediagonais do polígono como um todo, sendo assim desperdiçadas.Nossa solução é misturar as abordagens bottom-up e top-down. Aestratégia básica é construir uma aproximação grosseira de umatriangulação na fase bottom-up e então usar a informação que secalculou nesse processo para refinar a triangulação em uma fasetop-down. As principais ferramentas usadas são

i o polygon-cutting theorem, que nos fornece um esquema debalanceamento, e

5

ii o planar separator theorem [?], cujo papel é essencial na desco-berta de novas diagonais.

Aqui está uma overview mais detalhada do algoritmo. Comoobservado em [?] e [?], a triangulação de um polígono pode serderivada em tempo linear de seu mapa de visibilidade horizontal,algumas vezes chamado decomposição trapezoidal; é a partição dopolígono em obtida desenhando-se cordas horizontais a partir dosvértices. Podemos estender essa notação facilmente e falar, emgeral, do mapa de visibilidade de qualquer curva poligonal sim-ples (Fig. 2.1). Chazelle e Incerpy [?] mostraram como construiro mapa de visibilidade para uma curva com n vértices em tempoO(n log n) usando divisão e conquista. Seu algoritmo imita o mer-gesort: assumindo que n é uma potência de 2, no k-ésimo estágio(k = 1, 2, . . . , log n), a fronteira do polígono é decomposta em ca-deias de tamanho 2k, cujos mapas de visibilidade são construídosunindo-se os mapas obtidos em etapas anteriores. Cada estágiopode ser completado em um número linear de operações, de modoque o mapa de visibilidade do polígono toma tempo O(n log n).

O novo algoritmo segue o mesmo padrão: passa por uma up-hasede log n estágios, envolvendo o merging mescla dos mapas obtidosno estagio anterior. A novidade que trazemos para o processo é usaapenas aproximações grosseiras dos mapas de visibilidade duranteos merges. Deste modo podemos levar a cabo um estágio inteiroem tempo sublinear e superar a barreira n log n. As amostras sãosubmapas uniformes dos mapas de visibilidade; uniformes no sentidode que aproximam os mapas de vilibilidade igualmente bem em todaparte. Claro, ao fim, precisamos também de uma modo eficiente derefinar o submapa derivado para o polígono todo em um mapa devisibilidade completamente desenvolvido. Depois disso, obtém-se atriangulação em tempolinear. Para refinar o submapa, avançamospelos estágios em ordem reversa, (a fase down): cada transiçãorefina o submapa incrementalmente, até que alcançamos o estágioinicial, no qual o mapa de visibilidade completo finalmente emerge.

6 CAPÍTULO 1. INTRODUCTION

Fig. 1.1 ilustra o significado das fases up e down.Talvez seja agora o momento de pontederar se nossa abordagem

não está inerentemente fadada a falhar. Quanto sentido faz imitarmergesort quando nosso objetivo é vencer n log n? Qualquer tenta-tiva de acelerar o mergesort usando “amostras grosseiras” das listasa merge está trivialmente condenado. Então, o que é tão diferentea respeito de polígonos? A diferença parte da noção que chamamosconformalidade. Este é talvez o conceito mais importante em nossoalgoritmo, pois é precisamente onde mergesort e a triangulaçãotomam caminhos distintos. Lembre que o polygon-cutting theoremé um análogo geométrico do teorema do centróide para free trees:um mapa de visibilidade tem uma estrutura de árvore e, então,pode ser escrito como uma coleção de bolhas aproximadamente domesmo tamanho, elas mesmas conectadas formando uma árvore.Essas bolhas são os elementos constituintes de um submapa. Omerge de dois submapas pode assim ser viso como equivalente domerge de duas árvores. O equivalente no mergesort em uma sub-lista seria uma sublista (de alguma das listas que será mesclada)obtida tomando-se chaves a intervalos regulares. Note que a mes-cla de duas tais sublistas pode no pior caso produzir uma novalubslista cujos intervalos correspondentes apresentem até o dobrodo tamanho dos intervalos originais. Esse efeito de coarsening nosimpede de acelerar o mergesort , porque o conserto do dano podeenvolver o cálculo de medianas ou coisas de natureza semelhante,para as quais não se pode encontrar atalhos. Certamente, comoveremos, coisas igualmente ruins podem acontecer com submapas;o concerto do dano, contudo, pode ser feito pera simples adição decordas a submapas, o que pode ser feito de modo a consumir apenastempo sub-linear. Para tornar isso possível, precisamos primeiromanter a coarseness dos submapas sob controle, requerindo que aestrutura de árvore do submapa apresente grau limitado: em nossaterminologia, a “conformal” de fato significa grau menor ou igual a4. Restaurar a conformalidade depois de merging dois submapas écentral para o algoritmo e, como se deveria esperar, sua parte mais

7

delicada e sutil: pode ser visto como um análogo geométrico emduas dimensões de rotações em dynamic search trees.

Embora nosso algoritmo seja fruto do método mergesort-likede Chazelle e Incerpy, este vai muito além daquele. Po exemplo, oalgoritmo nunca mescla mapas de visibilidade, fazendo-o apenas comsubmapas (o que é feito de modo bastante distinto). Precisamostambém emprestar ideias de um certo número de outras fontes:como mencionamos antes, uma delas é o polygon-cutting theorem,e, mais especificamente, a decomposição hierárquica de polígonosde Chazelle e Guibas [?]. Há algoritmos ótimos para computartais decomposições [?, ?], mas métodos-padrão sub-ótimos servemperfeitamente a nossos propósitos. Merging de submapas requeruma primitiva para detectar novas cordas. No método Chazelle-Incerpy a detecção está limitada a domínios de tamanho fixo, dondepode ser feita ingenuamente. Mas aqui os domínios podem serarbitrariamente grandes, então precisamos de um método de ray-shooting sublinear. Isto não pode ser feito usando fast planar pointlocation. que é a bordagem seguida no algoritmo de Kirkpatricket al. [?]. A razão é que precisamos permitir a mescla de duasestruturas de point-location, e os métodos conhecidos, mesmo sodinâmicos, são inadequados para esse fim. Resolvemos o problemausando uma forma fraca de divisão e conquista baseada no planarseparator theorem de Lipton e Tarjan [?].

Capítulo 2

Mapas e Submapas devisibilidade

Seguindo a tradição de algoritmos de visibilidade, começamos res-tringindo sua aplicabilidade a polígonos em que nenhum par devértices distintos possui a mesma y-cordenada. Claro, a desculpapadrão ainda funciona: podemos facilmente contornar essa condiçaoaplicando as técnicas de perturbação simbólicas de [?] e [?]. Pas-sando agora para mapas de visibilidade, lembremos que, no métodoChazelle-Incerpi, cordas são estendidas apenas para o interior dopolígono, com uma regra especial para determinar o quanto elasdeveriam estender. Kirkpatrick et al. [?] usam o esquema mais sim-ples de estender cordas para ambos os lados. Isso equivale a pensara curva poligonal como um polígono fino colocado em um planocilíngrico que permite que as cordas “dêem a volta” pelo infinito.Pelas razões que damos abaixo, achamos mais conveniente colocarnossos objetos em um topological manifold , chamado plano esférico,que é equivalente a uma 2-esfera. Provas de corretude de polygonalmerging tendem a ser cheias de dolorosas análises de casos. Umarazão para isso é que essas provas frequentemente tentam estabele-

9

10 CAPÍTULO 2. MAPAS E SUBMAPAS DE VISIBILIDADE

cer fatos topológicos por meios geométricos, acrescentando assimcomplicação desnecessária. Ao nos restringirmos a consideraçõestopológicas tanto quanto possível, as provas se tornam muito maissimples, desde que, certamente, o espaço ambiente tenha a topologia“certa”.

Qual é a topologia certa neste contexto? Um problema como plano cilíndrico é que embora tenha um teorema da curva deJordan, as duas regiões criadas ao remover-se uma curva fechadasimples podem ser de três tipos:

1. um disco aberto,

2. um cilindro S1 × (0,+∞), ou

3. um cilindro perfurado.

Simplificamos tudo isso definindo nosso espaço ambiente como oplano esférico: isto é o espaço produto [−∞,+∞]2 com as seguintesregras de identificação

i (−∞, y) = (+∞, y),

ii (x,−∞) = (−x,−∞),

iii (x,+∞) = (−x,+∞),

para todo x, y ∈ [−∞,+∞]. O plano esférico é homeomorfo à2-esfera, então temos agora o mais legal dos teoremas da curvade Jordan: a remoção de qualquer curva fechada simples cria doisdiscos abertos.

A única dificuldade restante é a orientabilidade das curvas deJordan. Se fixamos uma orientação no plano esférico, a fronteirade qualquer região homeomorfa a um disco, sendo de codimensão1, tem uma orientação induzida chamada “horária”; a orientaçãoreversa é dita “anti-horária”. Por outro lado, dada uma curva deJordan, um percurso horário da curva se refere à orientação induzidapor um dos dois discos homeomorfos que ela delimita. A menos

2.1. O MAPA DE VISIBILIDADE 11

que algum desses discos já seja subentendido, escolhemos um semambiguidade fixando um ponto de referência em alguma parte doplano e olhando para o único dos dicos que não o contém. Claro,isso significa que devemos nos restringir a curvas que evitam o ditoponto, mas este é um pequeno inconveniente. Doravante assumimosque o ponto de referência está em (0,+∞). Desse modo, faz sentidofalar do percurso horário de uma curva de Jordan, sem referência àregião que ela encerra.

2.1 O mapa de visibilidade

Dada ma curva poligonal (aberta) C com vértices v1, . . . , vn, defini-mos o mapa de visibilidade de C, denotado V (C), como a subdivisãodo plano formada estendendo-se dois segmentos horizontais a partirde cada vértice vi, um em cada direção. Cada segmento, que chama-remos de corda, é estendido até que encontre outro ponto de C. Seo segmento fosse para o infinito, então ele na verdade dá a volta noplano esférico até que encontra C novamente. Adicionar cordas a Csubdivide o plano esférico em regiões: triângulos ou trapezóides comdois segmentos horizontais e dois segmentos não-horizontais, todosos quais estão possivelmente divididos em várias arestas colineares(Fig. 2.1).

Para distinguir entre os dois lados de uma aresta, damos a cadaaresta de C uma espessura infinitesimal de modo a transformar Cem um polígono simples muito fino. (Isto é apenas um artifícioconceitual, entã, em particular, nenhuma perturbação do polígonoprecisa ser feita no computador.) A fronteira desse polígono échamada borda dupla de C e é escrita ∂C. Por abuso de terminologianos referimos a ambos os lados da borda dupla como falaríamosdo lado esquerdo e direito de uma cobra; claro, isto tem sentidogeométrico mas não topológico. Cada vértice de C que não é umextremo local na direção y origina dois vértices companheiros em∂C, um de cada lado da curva (Fig. 2.2.1). Deste modo, cada vértice

12 CAPÍTULO 2. MAPAS E SUBMAPAS DE VISIBILIDADE

é incidente a exatamente uma corda (possivelmente a mesma paraambos os companheiros). Mas e quanto a extremos locais? Paracada tal vértice em C, se não for uma de suas duas extremidades,criamos um total de 4 vértices em ∂C (Fig. 2.2.2): dois pares decompanheiros de vértices duplicados; um par de cada lado de ∂C.Os vértices duplicados em um dado par aparecem um em seguidado outro ao percorrer-se ∂C. Por convenção, dizemos que um dessespares, aquele no lado “de dentro” da curva, dá origem a uma corda decomprimento nulo. Finalmente, como mostrao na figura Fig. 2.2.3,para cada extremidade de C criamos dois vértices companheiros;esses também podem ser chamados duplicatas já que estão um emseguida do outro além de estarem em lados diferentes de ∂C. Afigura Fig. 2.3 ilustra essas definições. Note que por simplicidadenão numeramos os vértices conectados a cordas de comprimentonulo, mas numeramos todos os extremos de cordas para uso futuro.Garantimos assim que cada vértice de ∂C incide em exatamente umacorda do mapa de visibilidade. Então, qualquer vértice — e de fatotambém qualquer ponto — de ∂C possui associada a si uma únicadireção de corda (esquerda ou direita). Falando grosseiramente,essa é a direção aponta para a esquerda de um observador quepercorra ∂C no sentido horário.

Se uma corda de V (C)possui p e q como extremidades, dizemosque p e q vêem um ao outro em relação a C, ou simplesmentese vêem, quando C está implícita. Equivalentemente, dizemosque p e q são mutualmente visíveis. De modo geral, se p e q sãodois pontos (não necessaramente vértices de ∂Ccom a mesma y-cordenada, dizemos que p e q se vêem com relação a C se um dossegmentos (relativamente abertos) ligando p e q fica completamentefora de C (visto como um polígono simples fino). Por extensão osegmento pq é também dito uma corda. Por exemplo, na Fig. 2.3os pontos rotulados 6 e 7 se vêem, enquanto os pontos 6 e 14, assimcomo os pontos 3 e 4 e os pontos 1 e 1′ não se vêem. Fechamosnossa discussão com um fato simples mas útil.Lema 2.1. Se removemos um par de pontos mutualmente visíveis

2.1. O MAPA DE VISIBILIDADE 13

da borda dupla de uma curva poligonal simples, então nenhumacorda pode conectar o pedaços de resultam dessa remoção.

Prova. Sejam C1 e C2 os dois pedaços da borda dupla que resultamda remoção de um par de pontos visíveis. Juntamente com C1 e C2,a corda c conectando os dois pontos subdivide o plano esférico emtrês regiões poligonais (i.e., regiões limitadas por curvas poligonaissimples), uma das quais é o próprio polígono infinitesimalmentefino C. Qualquer corda conectando C1 e C2 está fora do “polígono”C, então precisa cruzar c. Mas isso é impossível porque as cordassão horizontais.

A sequência de extremidades de vordas em V (C) encontradaquando se percorre ∂C no sentido horário é chamada enumera-ção canônica dos vértices de V (C): note que ela contém outrospontos além dos vértices de ∂C. Fig. 2.3 fornece a sequência1, 1′, . . . , 17′, 18, com os primos indicando vértices duplicados. Lem-bre que não numeramosas extremidades de ordas de comprimentonulo. Falando dos quais, node que cordas de comprimento nulocriam regiões vazias. Um percurso da borda dupla leva a umaenumeração canônica das regiões (com repetições). No caso daFig. 2.3, temos a lista (incluindo apenas as regiões não-vazias porsimplicidade)

(I,II,III,IV,VI,VII,VIII,VII,IX,VII,VI,

V,IV,III,X,XI,X,III,II,I,XII,I,XIII).

É fácil ver que o grafo dual da subdivisão é uma árvore, na-turalmente chamada a árvore de visibilidade de C. Esse grafo édefinido associando um nó distinto com cada região (vazia ou não)do mapa de visibilidade e conectando qualquer par de nós cujascorrespondentes regiões apresentam uma corda comum. Note queisso também inclui cordas de comprimento nulo. Fig. 2.1 mostra a

14 CAPÍTULO 2. MAPAS E SUBMAPAS DE VISIBILIDADE

árvore sem os nós associados a regiões vazias. Como qualsquer cuasregiões consecutivas na enumeração canôninca possuiem uma cordaem comum, a árvore de visibilidade é conexa. Por que não pode terciclos? Basta mostrar que remover qualquer corda ab torna o grafodesconexo.

Primeiro, assuma que a e b não são duplicatas um da outro(embora possam ser companheiros). Então, do lema 2.1, remover ae b divide a borda dupla em pedaços fechados quanto a visibilidade.Segue que a fronteira de qualquer região contém segmentos de apenasum dos dois pedaços, e entào pode ser classificada pelo pedaço aoqual esses segmentos pertencem. Qualquer corda separando umaregião associada com um pedaço de uma região associada com ooutro pedaço precisa unir dois pontos na junção entre os pedaços,e apena ab satisfaz esse requisito. Isso conclui o primeiro caso.Assuma agora que a e b sao duplicatas um do outro. Se a corda abpossui comprimento zero, então removê-la isola uma região vaziadas demais, e nosso claim vale. Suponha então que ab possuicomprimento não-nulo. Então a é ou o ponto mais alto ou o pontomais baixo de ∂C, donde remover ab desconecta a parte superior ouinferior do plano esférico das demais regiões. Isto completa a povade que a árvore de visibilidade é de fato uma árvore. (Há tambémuma prova topológica simples, que é dada no lema 2.2 abaixo.)

2.2 Submapas de visibilidade

Uma operação que será útil é a remoção de cordas de V (C). Antesde prosseguirmos, contudo, gostaríamos de nos preparar para apossibilidade de que V (C) tenha sido aumentado com algumasoras adicionais (algo que ira acontecer com frequência mais tarde).Obviamente, essas novas cordas não podem conectar vértices de ∂C(todas foram usadas já) mas sim pontos arbitrários na curva. Apesarde isso claramente afetar V (C) assim como a árvore de visibilidade,tudo o que já foi dito anteriormente a respeito de enumerações pode

2.2. SUBMAPAS DE VISIBILIDADE 15

ser trivialmente estendido para essa nova situação. Então, de agoraem diante, vamos tratar V (C) ou em sua forma original ou em suaforma aumentada. Especificaremos qual das duas se aplica sempreque a distinção precisar ser feita.

A operação que queremos discutir agora envolve a remoção deuma corda dade de V (C). Como V (C) pode ter cordas adicionais,precisamos ser cuidadosos a respeito do significado de uma remoção.Ua corda posui duas extremidades. nenhuma, uma, ou duas dasquais são vértices de ∂C. Então, a remoção de uma corda envolveremover não apenas a própria corda, mas também suas extremidadesque não são vértices de ∂C, e colar de de volta ∂C nesses pontos.Esta operação de simpeza visa a evitar a presença de vérticesstranded no meio de uma aresta de ∂C: em outras palavras, qualquervértice que não é um vértice de ∂C deve ser extremidade de umacorda não removida.

Remover uma ou mais cordas (de comprimento nulo ou não)de um mapa produz uma subdivisão poligonal do plano esférico,chamada submapa de V (C) (Fig. 2.4). A fronteira de uma regiãonão-vazia do submapa é uma sequência circular orientada de seg-mentos, chamados cordas de saída, alternando com pedaços de∂C e não de C. Por exemplo, vamos assumir que todas as cordasde comprimento nulo foram removidas no submapa da Fig. 2.4.Então a fronteira da região rotulada II cnsiste de um arco comduas arestas (iniciando no ponto grande), seguida por uma corda desaída, um arco de uma aresta, uma corda de saída, um arco de trêsarestas (e não de quatro!), uma corda de saída, um arco de umaaresta, e por fim uma corda de saída. Note que alguns arcos podemter comprimento nulo, como é o caso na região rotulada V. Comoilustrado na Fig. 2.4, um percurso de no sentido horário induz umpercurso da borda de cada região do submapa, que é anti-horáriocom relação à orientação da região. Mais formalmente, temos oseguinte fato.Lema 2.2. Seja A1, . . . , Ak a enumeração no sentido anti-horáriodos arcos (orientados) de uma região não-vazia do submapa (como

16 CAPÍTULO 2. MAPAS E SUBMAPAS DE VISIBILIDADE

induzido pela orientação da região), Então cada Ai está orientao emsentido hoário com relação a ∂C. Ademais, a sequência A1, . . . , Ak

também ocorre em sentido horário em ∂C.

Prova. A curva ∂C é homeomorfa a u círculo no plano esférico.Adicionar uma corda equivale topologicamente a conectar dois pon-tos no círculo por uma curva simples restando interiamente em umlado do círculo. O requisito de que todas as curvas sejam mutua-mente disjuntas induz um sistema de parêntesis que imediatamenterevela a estrutura de árvore do grafo dual. Isto é similar ao sis-tema de parentesis na ordenação de Jordan [?]. Como um exemplo,Fig. 2.5 exibe o equivalente topológico do submapa da Fig. 2.4. Sobesta perspectiva, o lema deve estar completamente óbvio.

Como era o caso com V (C), percorrer ∂C em sentido horárioinduz enumerações de vértices/regiões do submapa. Fig. 2.4 exibea enumeração de regiões: I,II,III,II,IV,II,V,II,I. (Lembre que essesubmapa em particular teve todas as cordas de comprimento nuloremovidas e assim não apresenta regiões vazias.) Pontos em negritomarcam os pontos no percurso em sentido horário nos quais regiõesenumeradas canonicamente são encontradas pela primeira vez. Umrequerimento importante é que a enumeração de vértices de umsubmapa liste apenas as extremidades de cordas de saída e assimpule vérios dos vértices de ∂C. Deste modo enumerações canônicasde qualquer tipo tomam tempo proporcional ao número de regiõese não ao número de vértices (que pode ser muito maior). Definimoso peso de uma região como 0 se a região é vazia, ou caso contráriocomo o número máximo de arestas de comprimento não-nulo emqualquer um de seus arcos. Por exemplo, as regiões I e II na Fig. 2.4têm pesos 4 e 3, respectivamente.

Embora pesos considerem apenas arestas de comprimento não-nulo, cordas de comprimento nulo (se houver) são levadas em consi-deração, já que separam arcos. Em outras palacras, um arco nuncacontém nenhuma corda, quer a corda tenha comprimento nulo ou

2.3. CONFORMALIDADE E GRANULARIDADE 17

não. Ademais, note o papel importante da borda dupla na definiçãodo peso de uma região. De fato, uma região pode ter um peso muitopequeno porque seus arcos são pequenos; mas isso não impede quequalquer um desses arcos possua um número enorme de vértices dooutro lado da borda dupla. Claro, porque vértices de ∂C possuemcompanheiros, os vértices xtras devem ser extremodades de cordasde saída.

Combinatoricamente, uma região corresponde a uma sub-árvoreda árvore de visibilidade de C. O grafo dual de um submapa é obtidocontraindo as arestas da árvore de visibilidade que correspondem àscordas removidas (Fig. 2.6). Por derivar da árvore de visibilidadevia operações graph-minor , o grafo dual do submapa é ele própriouma árvore (como ficou claro na prova do lema 2.2), que nossimplesmente chamamos a árvore do submapa. Note que, por outrolado, contrair qualquer aresta do mapa de visibilidade equivale aremover a corda correspondente do mapa de visibilidade. O pesode um nó naturalmente refere ao peso da região correspondente.

2.3 Conformalidade e Granularidade

Como não há dois vértices distintos de C com a mesma y-cordenada,o grau de qualquer nó em uma árvore de visibilidade não excede4. Mas não devemos esperar que isso seja sempre verdade paraárvores de submapa, e diferenciamos então as árvores de submapasconformais como aqueles cujo nó correspondente possui grau menorou ifual a 4. Por analogia com o polygon-cutting theorem [?] podemosdecompor um submapa conformal hierarquicamente. A ideia étomar o centróide da árvore do submapa e observar que existe aomenos uma aresta incidente a ele cuja remoção deixa duas sub-árvores,cada uma com um número de arestas até 3⁄4 do númerooriginal. Associando a aresta removida com a raiz de uma árvorebinária e prosseguindo recursivamente em cada um dos filhos daraiz gera uma decomposição em árvore do submapa. A árvore tem

18 CAPÍTULO 2. MAPAS E SUBMAPAS DE VISIBILIDADE

altura logarítmica no número de regiões (que é o número de cordasmais um). Os nós internos (respectivamente folhas) estão em bijeção

ckem bijeção com as cordas de saída (resp. regiões) do submapa. Fig. 2.7 ilustra

a correspondência (folas foram omitidas).Usando técnicas de rotulamento de árvore podemos encontrar o

nó centróide e, a partir dele, a primeira aresta a ser removida, emtempo linear. Prosseguindo recursivamente obtemos um algoritmode tempo O(m logm+ 1) para calcular a decomposição e árvore deum submapa com m regiões. Usamos o resultado abaixo porqueé simples e prático. Métodos ótimos existem, mas eles são todosrazoavelmente complicados e desnecessários aos nossos propósitos [?,?].

Um último ponto sobre classificação relacionado ao nosso de-sejo de tomar submapas que sejam aproximações grosseiras, masuniformes, de mapas de visibilidade. Dizemos que um submapa éγ-granular se

(i) todo nó de sua árvore possui peso no máximo γ e

(ii) contrair qualquer aresta incidente a al menos um nó de graumenor do que 3 produz um nó de peso > γ.

Note que este peso pode ser menos do que a soma dos pesos dosdois nós da aresta contraída. Isto tanto porque os arcos incidentesà corda removida não determinavam os pesos, ou, o que é maisinteressante, porque uma ou ambas as extremidades da corda podemnão ser vértices de ∂C e assim desaparecem. Se apenas a condição(i) vale, então o submapa é γ-semigranular. Adicionar a condição (ii)torna a semigranulariade maximal em algum sentido. Finalmente,por default, se (i) vale mas o submapa não possui corda de saída,ainda assim é dito ser γ-granular. O resultado a seguir afirmaque, como esperado, um submapa conformal e γ-granular é maiseconomicamente armazenado do que o mapa de visibilidade inteiro,por um fator γ.

2.4. QUESTÕES DA REPRESENTAÇÃO 19

Lema 2.3. Se C é uma curva poligonal com n vértices, qualquersubmapa γ-granular conformal do (possivelmente aumentado) mapade visibilidade de C possui O(n/γ + 1) regiões e cada região élimitada por O(γ) arestas.

Prova. Podemos assumir quea ávore do submapa possui ao me-nos uma aresta, caso contrário o lema é trivial por causa da γ-granularidade. Entre as arestas da árvore, seja E o conjunto daque-las incidentes a al menos um nó de grau menor do que 3. É trivialmostrar por indução no tamanho da árvore que E é responsável porpelo menos uma fração fixa de todas as arestas. Agora, contrairqualquer aresta em E, ou equivalentemente, remover uma cordaassociada com E produz uma região mesclada de peso maior do queγ, implicando que ela possui um arco com mais do que γ arestasde comprimento não-nulo. Como um vértice de C pode dar origema no máximo 4 vértices de ∂C, e cordas removidas não deixamvértices-extra exceto os de ∂C, tal arco deve possuir ao menos Ω(γ)vértices distintos de C. Se contrair qualquer aresta de E sempre pro-duzisse uma região mesclada disjunta, então segue do princípio dacasa dos pombos que E, e assim a árvore inteira, possui O(n/γ + 1)arestas. Infelizmente, duas arestas de E podem produzir regiõesmescladas intersectantes (i.e., se têm um nó comum). Da conforma-

ckintersectanteslidade do submapa, contudo, sabemos que um vértice qualquer de

C pode ser usado no máximo um número constande de vezes nesteargumento de contagem, donde E tem de fato O(n/γ + 1) arestas ea primeira parte do lema está estabelecida. A segunda parte derivada conformalidade do submapa, que garante que há um númerolimitado de arcos por região e, assim, que o número total de arestasé no máximo proporcional ao peso da região.

2.4 Questões da representação

Como representamos mapas de visibilidade e submapas como estru-turas de dados? Primeiro descrevemos nosso modo de representação,

20 CAPÍTULO 2. MAPAS E SUBMAPAS DE VISIBILIDADE

e então apontamos algumas de suas idiossincrasisas e explicamosporque são necessárias. Seja P a curva poligonal de entrada (aquelacujo mapa de visibilidade é buscado) e seja C a subcadeia de Pcujo mapa (ou submapa) de visibilidade desejamos representar. As-sumimos que P é aberta; isso não é restritivo já que um pequenofuro pode sempre ser feito se for fechada. Assumimos que as arestasde P estã armazenadas em uma tabela (a tabela de entrada) naordem em que ocorrem pela fronteira de P . (Uma lista duplamenteligada serve também.) Note que a noção da borda dupla não precisaser codificada explicitamente, i.e., nenhuma aresta é duplicada natabela. A tabela de entrada é somente-leitura: ela não é jamaismodificada ou mesmo copiada. Um submapa de visibilidade V (C)é representado por sua própria estrutura de dados: arcos são repre-sentados apontando diretamente para a tabela de entrada. Maisprecisamente, cada arco é representado por uma estrutura de arcoseparada. Arcos de comprimento nulo podem ser representadosexplicitamente, então vamos assumir que o arco possui comprimentonão-nulo. Sejam e1, . . . , et as arestas do arco em sentido horáriona borda dupla, onde e1 e et são arestas ajacentes às duas cordasconectadas pelo arco. Se t = 1, então a estrutura de arco consistede um simples ponteiro para a aresta e de P na tabela de entradaque contém e1. Como e1 é uma aresta da borda dupla, tambémprecisamos indicar por um flag a qual lado de e nos referimos. Nãoprecisamos armazenar os extremos do arco porque as codas cuidamdisso. Se t > 1, armazenamos a mesma informação como acimamas agora relativamente a tanto e1 como et nessa ordem. Dizemosque o submapa (ou mapa) é dado na forma normal se a seguinteinformação está disponível:

(i) A árvore do submapa (ou mapa) está representada por demodo usual por adjacências entre arestas/nós.

(ii) Cada aresta da árvore contém um registro descrevndo a cordacorrespontente, assim como ponteiros para as estruturas dos

2.4. QUESTÕES DA REPRESENTAÇÃO 21

dois, três ou quatro arcos a ela adjacentes. Por outro lado,cada estrutura de arco aponta para o nó da árvore cuja regiãocorrespondente é incidente ao arco em questão.

(iii) As estruturas de arcos são armazenadas em uma tabela (aarc-sequence table) em ordem correspondente a percorrer aborda dupla de ∂C segundo a ordem canônica. També, osextremos de C estão identificados por apontadores apropriadospara a tabela de entrada assim como apontadores para asestruturas de arco cujos arcos correspondentes passam pelasextremidades.

(iv) Se o submapa é conformal, entã sua decomposição emárvoedeve estar disponível.

Escolhemos o que pode parecer uma representação enrolada deum submapa para que ocupe espaço proporcional não ao númerode arestas no submapa mas em vez disso ao número de regiões(que é da mesma ordem de magnitude que o número de cordase arcos). É essencial evitar excessiva duplicação de informaçãoporque precisamos representar uma coleção de submapas cujo nú-mero de características distintas é apenas O(n), mas cujo tamanhocombinado, contando redundância, é Θ(n log n). Note que nossarepresentação é poderosa o bastante para que possamos fazer umaenumeração canônica dos vértices/regiões em tempo ótimo. Sedesejássemos, também poderíamos enumerar todos os vértices de∂C em sentido horário diretamente a partir de uma enumeraçãocanônica dos vértices do submapa, já que qualquer arco pode serexplicitamente reconstruído a partir da informação sucinta dadapela estrutura de arcos: basta explorar a tabela de entrada entreas posiçõers indicadas pelos dois ponteiros da estrutura de arco.Note que se deve tomar cuidado já que um arco pode “dar a volta”pelos lados de ∂C, algo que chamamos double-backing . Isso podeser detectado quando atravessamos o arco assim que alcançamosuma aresta de P incidente a uma extremidade de C.

22 CAPÍTULO 2. MAPAS E SUBMAPAS DE VISIBILIDADE

Talvez uma tarefa menos óbvia seja recuperar as estruturas dearcos correspondentes a um arco, dado uma de suas arestas. Maisespecificamente, suponha que é dada uma aresta e de C e um pontoq nela. A questão é encontrar as estruturas de arco de todos aquelesarcos do submapa que passam pelo ponto q. Ao dizer “passar por”,não nos importa se o arco está em qualquer lado particular daborda dupla, então, por exemplo, se q não é extremidade de cordaalguma no submapa, então há no máximo dois arcos distintos aencontrar. De outra forma, há até seis deles, dois dos quais têmcomprimento zero: este pior caso ocorre quando q coincide com umvértice de C que é um extremo local na direção y. Como sabemosa localização dos dois extremos de C na arc-sequence table (i.e.,quais arcos passam por eles) podemos conceitualmente quebrar asequência circular de arcos em duas sequencias lineares e efetuarem cada uma uma busca binária usando o nome da aresta comocampo. Ou a busca nos leva a uma única estrutura de arco, em cujocaso estamos feitos, ou caso contrário a um intervalo de estruturasde arco contíguas: isto pode acontecer se e contribui com diversosarcos. Podemos eliminar a ambiguidade perseguindo adiante abusca, usando agora, digamos, a y-cordenada de q como campo. Otempo total é logarítmico no número de arcos. Essa operação serábastante útil depois quando quisermos navegar em um submapaatravés de seus arcos: nós a chamamos dupla identificação de umponto de C.

Dissemos repetidamente que um submapa possui uma estruturade árvore. Agora vamos mudar de perspectiva por um momento eobservar um submapa como uma divisão padrão do plano, sem dis-tinguir entre cordas e arestas de arcos. Há várias representações degrafos planares [?, ?, ?] que nos permitem navegar pela subdivisãopor arestas em tempo constante por passo dado. Representaçõesna forma normal não são tão poderosas. um problama aparece setentamos cruzar de um lado a outro de um arco, digamos, em umalinha reta. Para encontrar em que região estamos para entrar épreciso fazer uma dupla identificação. A dificuldade aqui é que

2.5. UM LEMA TOPOLÓGICO 23

diferentemente do que é geralmente feito em representações-padrãode grafos nós não mantemos informação sobre adjac~encia de re-giões e arestas (exceto para cordas). Mais importante ainda, nãofornecemos uma correspondência explícita entre as característicasdos dois lados de uma aresta de C. Por razões que se tornarão maisclaras depois, seria uma ideia bem ruim tentar fazer isso.

2.5 Um lema topológico

Fechamos esta discussão de submapas de visibilidade provandoum resultado da topologia de regiões e cordas, que usamos paraestabelecer a curretude de nosso algoritmo para merging submapas.Seja D um disco fechado no plano estérifo, D sua fronteira, e sejaab uma cora diametral de D. Tome dois pontos distintos c e d em Dtais que a, c, b ocorrem em sentido horário (em relação a D), e sejaA a curva simples que fica em D e vai de c a d. Considere o arcocircular que parte em sentido horário de d para c e seja Bi(i = 1, 2)