Proximidade: Algoritmos Fundamentais

Neste post estaremos apresentando uma grande classe de problemas que envolvem a proximidade de pontos no plano e nosso objetivo será o de lidar com todas essas tarefas aparentemente não relacionados através de um único algoritmo, que descobre, processos e armazena de forma compacta toda informação de proximidade relevante. Para fazer isso, utilizaremos um objeto matemático clássico, o diagrama de Voronoi, e vamos transformá-lo em uma estrutura computacional eficiente que permite grande melhoria sobre os melhores algoritmos previamente conhecidos. Este post foi desenvolvido a partir do conteúdo do capítulo 5, Proximidade: Algoritmos Fundamentais do livro Computational Geometry an Introduction, dos autores Franco Preparata e Michael Ian Shamos

Problema 1: (Par mais próximo): Dados N pontos no plano, encontre dois que estejam mais próximos.

Este problema é tão facilmente declarado e importante que devemos considerá-lo como uma das questões fundamentais de geometria computacional, tanto do ponto de vista de aplicações quanto de puro interesse teórico. Por exemplo, uma aplicação em tempo real é fornecida pelo problema de controle de tráfego aéreo: com alguma simplificação, os dois aviões que estão em maior perigo de colisão são os dois mais próximos.

A questão algorítmica central é se é necessário examinar cada par de pontos para encontrar a distância mínima assim determinada. Isto pode ser feito em tempo O (dN²) em  d dimensões, para qualquer d. Em uma dimensão de um algoritmo mais rápido é possível, com base no fato de todos os pares de pontos mais próximos devem ser consecutivos na ordem de classificação. Podemos, assim, classificar os dados N números reais em O (N logN) etapas e executar uma varredura linear de tempo da seqüência ordenada (x₁,x₂,...,x_n) computando x_{i +1} = 1, ..., N - 1. Este algoritmo,como será mostrado adiante, é executado em tempo ótimo.

Problema 2: (Todos vizinhos mais próximos). Dados N pontos no plano, encontre o vizinho mais próximo de cada ponto. 

O "vizinho mais próximo" é uma relação em um conjunto S de pontos como a seguinte: o ponto b é o vizinho mais próximo do ponto a, representado como b -> a , se dist(a,b) = min dist(a,c), onde c pertence a S - a.

Note que não é necessariamente verdade que se a -> b então b -> a e que um ponto qualquer não tem necessariamente apenas um único vizinho mais próximo. A solução do problema 2 é um conjunto de pares ordenados (a,b) onde a -> b.

Problema 3: (Árvore de Abrangência Euclidiana Mínima). dado N pontos no plano, construir uma árvore de comprimento total mínimo cujos vértices são os pontos dados.

Para solucionar este problemas devemos construir uma lista de N -1 pares de pontos que compreende as arestas da árvore. Tal árvore é mostrada na Figura 5.2. Este problema é um componente comum de aplicações que envolvam redes. Se alguém deseja criar um sistema de comunicação entre os nós N requerem cabos de interconexão, usando a Árvore de Abrangência Euclidiana Mínima irá resultar numa rede de custo mínimo.

Problema 4: (Triangulação). Dado N pontos no plano, juntá-los por segmentos de linha que não se intersectam, de modo que cada região interna ao fecho convexo seja um triângulo.

Sendo um grafo planar, uma triangulação em N vértices tem no máximo 3N - 6 arestas. Uma solução para o problema deve conter pelo menos uma lista dessas bordas.

Uma triangulação é mostrada na Figura 5.4. Este problema coloca-se no método de elementos finitos [Strang-Fix (1973), Cavendish (1974)] e em interpolação numérica de dados bivariados, quando os valores da função estão disponíveis em N pontos de dados irregularmente espaçados (xi,yi) e uma  aproximação da função para um novo ponto (x, y) for desejada. Um método de fazer isto é por interpolação linear por partes, na qual a superfície é função representada por uma rede de faces triangulares planas.

Problema 5: (Busca de Vizinho Mais Próximo). Dados N pontos no plano, com preprocessamento permitido, com quanta rapidez pode ser encontrado um vizinho mais próximo de um dado ponto p?

Podemos resolver este problema em tempo O(dN) em d dimensões, mas estamos interessados em usar preprocessamento para aumentar a velocidade da busca. Há uma variedade de aplicações para o qual busca rápida é mais importante do que o problema de classificação.

Um método de classificação é a regra do vizinho mais próximo [Duda-Hart (1973)], no qual estados de quando um objeto deve ser classificado variam com o número de objetos conhecidos da população. Uma aplicação semelhante ocorre na recuperação de informações, onde o registro que melhor atende a consulta é recuperado [Burkhard-Keller (1973)]; [Fricdman-Bentley-Finkel (1977)]. Se muitos objetos devem ser processados seja em tarefas de classificação [Duda-Hart (1973)] (reconhecimento de voz, identificação de partículas elementares, etc.) ou em tarefas de recuperação (melhor resposta recuperada), devemos estar preparados para realizar busca de vizinhos mais próximos com rapidez.

Problema 6: (Busca de K-Vizinhos Mais Próximos). Dado N pontos no plano, com o pré-processamento permitido, com que rapidez podemos encontrar os k pontos mais próximos para um novo ponto dado q?

Os  k-vizinhos mais próximos têm sido usados ​​para interpolação e contorno [Davis (1975)] e para a classificação (a regra k-vizinho mais próximo é mais robusta do que apenas olhar para um único vizinho).

A Abordagem de Local para Problemas de Proximidade: O Diagrama de Voronoi

Apesar da abordagem de dividir e conquistar utilizada para o problema do par de pontos mais próximo é bastante encorajadora, ela ainda não consegue resolver todos os problemas de  vizinhos mais próximos, que parecem ser apenas uma simples extensão. Na verdade, se tentarmos criar a recursão análoga para todos os vizinhos mais próximos, vemos que a forma natural de dividir o problema não induz dispersão, e não há nenhuma forma aparente de realizar a etapa de fusão em menor tempo do que tempo quadrático.Por outro lado, uma heurística valiosa para a concepção de algoritmos geométricos é olhar para a definição de "local" e tentar organizá-los em uma estrutura de dados. Numa formulação bidimensional, queremos resolver,

Problema 8 (Local de Proximidade). Dado um conjunto S de N pontos no plano, para cada ponto p em S qual é o local de pontos (x,y) no plano que estão mais próximos de p do que qualquer outros pontos de S?

Note-se que, intuitivamente, a solução do problema acima é uma partição do plano em regiões (cada região, sendo o local geométrico dos pontos (x, y) mais perto de um ponto de S do que de qualquer outro ponto de S). Observamos também que, se conhecemos esta partição, procurando-a (isto é, pela localização de um ponto q em uma região da partição), podemos resolver diretamente a busca do vizinho mais próximo (Problema 5).

Vamos agora analisar a estrutura da partição do plano. Dado dois pontos, p_i e p_j o conjunto de pontos mais próximos de p_i do que p_j é apenas a metade do plano que contém p_i que é definido pela mediatriz p_ip_j. Vamos chamar este semi-plano de H (p_ip_j). O local geométrico dos pontos mais perto de p_i do que qualquer outro ponto, que denotamos por V(i), é a interseção de N - 1 semiplanos, e é uma região poligonal convexa, não tendo mais de n - 1 lados.V(i) é chamado de polígono de Voronoi associado com p_i.

Exemplo de cálculo da triangulação de Delaunay diretamente, usando a abordagem incremental randomizada.

Inicialmente iremos criar um triângulo largo que deverá conter o conjunto de pontos P. Iremos adicionar pontos extras p-1 e p-2 que, juntos com o ponto de mais alta coordenada y P0 de P, formarão o triângulo que irá conter todos os demais pontos.

Isto significa que nós iremos agora computar a triangulação Delaunay de P∪{p−1, p−2} ao invés da triangulação de Delaunay de P. Depois descartaremos p-1 e p-2 juntamente com todas as arestas incidentes para obter a triangulação Delaunay de P.

Para este trabalho, temos que escolher p-1 e p-2 o mais distantes possível, para que não destruam nenhum triângulo de Delaunay de P. Devemos garantir também que eles não caiam em nenhum círculo definido por três pontos em P.

O algoritmo é randomizado incremental, de modo que adiciona os pontos em ordem aleatória e mantém uma triangulação de Delaunay do conjunto de pontos atual. Considere a adição de um ponto pr.
Primeiro, encontre o triângulo da triangulação atual que contém pr e adicione arestas de pr para os vértices deste triângulo.
Se acontecer de pr cair em uma aresta e da triangulação, temos que adicionar arestas de pr para os vértices opostos nos triângulos que compartilham e. A figura a seguir ilustra estes dois casos.

Agora temos uma triangulação, mas não necessariamente uma triangulação Delaunay. Isto porque a adição de pr pode ter tornado ilegais algumas das arestas existentes. Para resolver este problema, chamamos o procedimento LegalizeEDGE para cada aresta potencialmente ilegal. Este programa transforma arestas ilegais em arestas legais pela rotação de arestas.

Algoritmo de Triangulação Delaunay para um conjunto de pontos P de n+1 pontos

Em seguida, discutiremos os detalhes de transformar a triangulação chegarmos após a linha 9 (ou
linha 14) em uma triangulação Delaunay.

Sabemos do Teorema 9.8 que a triangulação é uma triangulação de Delaunay, se todas as suas bordas são legais. No espírito do algoritmo LEGALTRIANGULATION, nós, portanto, iremos trocar as bordas ilegais até a triangulação ser legal novamente.

A questão que permanece é que as extremidades podem tornar-se ilegais, devido à inserção de pr. Observe-se que uma aresta do pi pj que era legal antes só se torna ilegal se um dos triângulos incidentes for alterado.

Assim, apenas as arestas dos novos triângulos precisam ser verificadas. Isto é feito usando a rotina LegalizeEDGE, que testa e possivelmente rotaciona uma borda.

Se LegalizeEDGE vira uma aresta, outras arestas podem se tornar ilegal. Portanto LegalizeEDGE chama a si mesmo de forma recursiva para todas as potenciais arestas ilegais.

Computando Triangulação Delaunay usando Fecho Convexo

Há uma conexão entre o fecho convexo e a triangulação Delaunay, que foi descoberta em 1979 por Kevin Brown e completamente desenvolvida por Herbert Edelsbrunner e Raimund Seidel no início dos anos 80. O centro desta conexão envolve o paraboloide

 Seja S um conjunto de pontos no plano xy, sem 4 pontos co-circulares. Associado a cada site (x,y) um valor de "altura de terreno" de x2 + y2 . Este local estará exatamente dentro de um paraboloide. Agora encontre o fecho convexo deste conjunto de pontos em R3. Descarte as "faces de cima" deste fecho, aquelas faces que são visíveis olhando diretamente para baixo do eixo z do alto. Estas faces são chamadas de fecho convexo superior, enquanto as faces restantes são chamadas de fecho convexo inferior. O impressionante resultado da conexão entre o fecho convexo e a triangulação Delaunay é dado pelo seguinte teorema:

Dado um conjunto de pontos S em um plano xy, a triangulação Delaunay Del(S) é exatamente a projeção para o eixo xy do fecho convexo inferior dos pontos (x,  y, x2+y2).

A figura a seguir mostra 10 pontos no plano cuja triangulação resulta da projeção do fecho convexo inferior destes pontos localizados no paraboloide. A marca do círculo no plano mostra a origem em R2, o ponto no qual o paraboloide toca o plano.

Do cálculo multivariado, a equação da tangente plana ao ponto (a,b) é dada por:

Se este plano for deslocado para cima (na direção de z) pela distância de r2, obtemos um novo plano p dado por

Da geometria cônica, este plano p intercepta a paraboloide ao longo de uma elipse. A projeção dessa elipse sobre o plano xy obtida resolvendo as equações (4.1) e (4.3) produz

Prova: Escolha uma face t do fecho convexo inferior, e deixe π ser o plano definido pelos três pontos de T no parabolóide. Nós podemos mudar esse plano para baixo (na direção z) até que seja tangente à

parabolóide. Sejam (a, b​​, a2 + b2) o ponto de tangência e deixe r2 ser a quantidade de deslocamento para baixo em π. A equação do plano π é então dada por (4.3). 

Pela discussão anterior, a projeção no plano xy dos três pontos que definem t encontra-se em um círculo de raio r dada pela equação (4.4). Desde que t é uma face inferior do fecho convexo, todos os outros sites na paraboloide encontram acima de π, o que implica que se projetam para fora deste círculo de raio r. Portanto, este círculo determinado por t está vazio. pelo Teorema 3.53, a projeção de t para o plano xy é um triângulo Delaunay. Uma vez que isto é verdade para todos as faces do fecho convexo inferior, a projeção plena produz a triangulação de Delaunay.

Geometria Voronoi

Definição: A região Voronoi Vor(p) de um site p em S é

onde ||p-q|| representa a distância Euclidiana entre os pontos p e q no plano.

Vor(p) representa o conjunto de todos os pontos x que estão mais próximos de p do que qualquer outro site q em S. Os pontos que se encontram na fronteira entre as regiões não tem um único site mais próximo. O diagrama de Voronoi é a coleção destas fronteiras: o conjunto de todos os pontos no plano que tem mais de um site vizinho mais próximo.

Se existe apenas dois sites p e q em S, o diagrama de Voronoi será simplesmente o segmento de reta bissetor perpendicular ao segmento pq. Este bisetor corta o plano em 2 regiões onde a região Voronoi de p é a metade do plano que contem p:

Se S tem numerosos sites, então é necessário comparar as distâncias dos pontos entre p e os outros sites de S. Isto produz os seguintes resultados:

Teorema 4.1 - A região Voronoi Vor(p) é a intersecção de todos os semiplanos H(p,q), onde q é algum outro site de S.

Um dos resultados fundamentais da Geometria Discreta é que

Teorema 4.2 - A intersecção de qualquer (não necessariamente finito) conjunto de objetos convexos é convexo.

Como todos os semi-planos são regiões convexas, o seguinte corolário é imediato

Corolário: Todas as regiões de Voronoi são convexas.

Vamos supor que existam apenas 3 sites p, q e r no conjunto de pontos S. O diagrama de Voronoi é formado por 3 bissetores perpendiculares dos segmentos pq, pr e qr. É possível que estes bissetores não necessáriamente se cruzem em um ponto, como na figura 1(a)? A resposta é NÃO, pois de acordo com um teorema de Euclides (Elementos, Livro IV, Proposição 5). Euclides provou que os bissetores perpendiculares dos lados de um triângulo  - pqr no nosso caso, mostrado em 1(b) - devem todos passar por um único ponto.De fato este ponto é um Vértice Voronoi, é o centro do único círculo circunscrito pelo qual passam os vértices do triângulo, como ilustrado em 1(c).

Figura 1 - Bissetores e círculos circunscritos em 3 sites

O que acontece com 4 ou mais sites?
Considere os dois diagramas na Figura 2. O lado esquerdo mostra um caso em que quatro sites do ponto estão posicionados sobre a  mesma circunferência circunscrita, isto acontece quando o vértice Voronoi  tem
grau 4. No entanto, se um dos locais (tal como a parte superior esquerda) é movido ligeiramente, como na figura da direita, então o grau-4 de Voronoi se divide em dois vértices graus-3. Assim, a imagem da direita é, em certo sentido, "Genérica", enquanto a da esquerda é degenerada.

                                             Figura 2 - Os diagramas Voronoi para 4 pontos

Interseções de bissetores criam vértices de Voronoi. No entanto, certamente, nem todos esses cruzamentos tornam-se vértices Voronoi. Existe uma maneira fácil de descobrir quais os pontos no plano se tornarão vértices Voronoi? O teorema a seguir responde a esta afirmativa:

Teorema 4.6 - Seja S um conjunto de pontos com diagrama Voronoi Vor(S). Um ponto v é um vértice Voronoi de Vor(S) se e somente se existir um círculo centrado em v com 3 ou mais sites em sua fronteira e nenhum site em seu interior.

Teorema 4.9 - Seja S um conjunto de pontos com diagrama Voronoi Vor(S), e seja e um subconjunto conectado do bissetor entre os sites p e q de S. Então e é uma aresta de Voronoi de Vor(S) se e somente se para cada ponto x em e, o círculo centrado em x atravessando de p e q não contem nenhum outro site de S em seu interior ou na fronteira.

Teorema 4.10 - Um diagrama de Voronoi Vor(S) de um conjunto de pontos S tem linha de aresta infitita se e somente se todos os sites de S são colineares.

Corolário 4.11 - Para um conjunto de pontos S, o diagrama de Voronoi Vor(S) é desconectado se  e somente se todos os sites de S são colineares.

Teorema 4.12 - Seja S um conjunto de pontos com n > 2 sites, então Vor(S) tem pelo menos 2n - 5 vértices de Voronoi e 3n - 6 arestas de Voronoi.

Triangulação Delauynay

Consideremos um conjunto de pontos S interpretados como estando em uma "posição geral", o que significa que não existem 3 pontos colineares ou 2 pontos não compartilham a mesma coordenada x e que não existem 4 pontos cocirculares.

Seja T uma triangulação dos pontos do conjunto S e suponha que T possui n triângulos. A sequência de ângulos (a1,a2,a3,...,an) de T é a lista de todos os ângulos de T ordenados do menor para o maior.

Usando a sequência de ângulos podemos comparar duas diferentes triangulações de S. Como o número de triângulos de qualquer triangulação de S é uma constante, todas as triangulações possuem sequência de ângulos do mesmo comprimento.

Então (20º, 30º, 45º, 65º, 70º, 130º) é melhor do que (20º, 30º, 45º, 60º, 75º, 130º) porque 65º > 60º na primeira posição em que as sequências diferem.

A melhor triangulação é o que procuramos, mas como é que vamos encontrá-la? Acontece que existe uma maneira elegante de obter a melhor triangulação via inversão de arestas. Começamos com uma definição.

Definição: Seja e uma aresta de uma triangulação T1, e seja Q um quadrilátero em T1 formado pelos 2 triângulos que têm e como aresta comum. Se Q e convexo, deixe T2 ser a triangulação depois de inverter a aresta e em T1. Dizemos que e é uma aresta legal se T1 for maior ou igual a T2, caso contrário e é uma aresta ilegal.

Para obter a melhor triangulação do conjunto de pontos S devemos evitar o surgimento de arestas ilegais nas triangulações.

Definição: Para um conjunto de pontos S, uma triangulação Delaunay de S (Del(S)) é uma triangulação onde ocorrem apenas arestas legais.

Algoritmo de Inversão de Arestas: Seja S um conjunto de pontos em "posição geral", sem 4 pontos cocirculares. Inicie com uma triangulação T. Se T tem uma aresta ilegal, inverta a aresta e obtenha uma aresta legal. Continue invertendo arestas ilegais, movendo-se pelas arestas do grafo de S em qualquer ordem até não restarem mais arestas ilegais.

No algoritmo de Delaunay proposto, para realizar o cálculo da aresta legal será necessário a inversão de uma diagonal, o quê envolverá a comparação de 12 ângulos em duas sequências de 6 ângulos. Há uma maneira mais simples de fazer este teste usando círculos baseado em uma extensão da um teorema clássico da geometria planar:

Teorema 3.49(Thales) Para três pontos P, Q e B em um círculo, e A dentro e C fora do círculo, o ângulo PAQ é maior que  PBQ que é maior que PCQ.

Esboço da Prova: Seja O o centro do círculo. Os 3 segmentos OP, OQ e OB são radianos e tem igual comprimento. Então os triângulos POB e QOB são isóceles. Sendo assim, não é difícil mostrar que independente da posição de B no arco do círculo, o ângulo POQ é duas vezes maior que PBQ. De fato, este é o teorema de Euclides (Elementos, Livro III, Proposição 20): um ângulo inscrito em um círculo tem metade do ângulo central subtendido o mesmo arco. Isto pode ser utilizado para declarar que o ângulo PAQ é maior que PBQ e que PCQ é menor que PBQ.

Diagrama de Voronoi - Algoritmo de Linha de Varredura

Algoritmo de Linha de Varredura

Dado um conjunto de p1,...,pn de pontos no plano, queremos construir um diagrama de Voronoi varrendo uma uma linha horizontal entre os pontos, mantendo o que foi visto ao longo do caminho. 

Para isso, precisamos usar uma estratégia adicional envolvendo parábolas. Parábolas são úteis para este problema de linha de varredura porque para qualquer ponto pi, há uma parábola separando pi da linha de varredura de tal maneira que cada ponto da parábola é eqüidistante tanto de p quanto da linha de varredura. Assim, quando a linha de varredura atinge um novo ponto de pj, sabemos, com base na parábola associada com cada ponto, qual é o ponto médio entre pi e pj.

O algoritmo irá varrer uma linha horizontal de baixo para cima, criando uma parábola para cada ponto, tal que para cada posição da linha de varredura, cada ponto é o foco de sua parábola e a diretriz da parábola é a própria linha de varredura. A parábola se torna mais aberta a medida que a linha de varredura avança para o topo do plano

Figura 1 

Em qualquer fase do processo, o algoritmo assemelha-se o que vemos na Figura 2.

Figura 2

Acima da a linha de varredura está um conjunto de sites não visitados, e todos os sites abaixo da linha de varredura já foram visitados pelo algoritmo. Os arcos mais próximos da  linha de varredura criar uma "fronteira de onda" (wavefront),  bloqueando a vista de outros arcos. Os pontos na "fronteira da onda" onde os arcos se encontram são chamados de pontos de interrupção, e note que cada ponto de interrupção é equidistante de seus correspondentes locais. Cada ponto já ultrapassado pela "fonteira da onda" é conhecido por pertencer a uma região específica de Voronoi.

Considere as seguintes observações:

1. Com o avanço da linha de varredura, um novo arco (de alguma parábola) é adicionado para a "fronteira da onda" somente quando a linha de varredura toca algum site. Isto é chamado de evento de site.
2.  A única maneira que um arco desaparecer a partir da frente de onda é quando dois arcos adjacentes de cruzam em um ponto comum. Chamamos a isto um evento de círculo

Estrutura de Dados

Como estamos interessados em ambos eventos de site e de círculo, vamos usar duas

estruturas de dados para armazenar as informações recuperadas durante todo o processo. 

A primeira estrutura de dados será uma árvore binária balanceada T usado para armazenar a "fronteira da onda". As folhas da árvore serão os arcos que compõem a "fronteira da onda" e os nós internos de T serão os pontos de interrupção (interseções de arcos).

Precisamos ser capazes de realizar as seguintes operações em T:

1. Inserções: quando um novo arco for adicionado na "fronteira da onda"
2. Deleções: quando um arco tornar-se invisível para a linha de varredura e não fizer mais parte da "fronteira da onda"
3. Busca: Para qualquer linha vertical que quisermos saber qual arco cruza.

A segunda estrutura de dados que queremos usar é uma fila de prioridade Q para armazenar os eventos encontrados. As operações que nós gostaríamos de usar são os seguintes:

1. Inserção: para incluir novos eventos quando ocorrerem no processo
2. Deleção: depois de processar o evento, ele não mais é necessário e deve ser excluído
3. Sucessor: após processar um evento, devemos processar o evento seguinte na fila baseado na posição do ponto na coordenada Y

Complexidade

No pior caso, existem 2n -1 arcos na "fronteira de onda" ao mesmo tempo. Isto ocorre quando cada arco está sobre a "fronteira de onda", mas um é dividido por outro arco da "fronteira de onda"). Então a árvore balanceada contém O(n) elementos. Como cada operação que queremos realizar em T leva não mais que tempo O (log n) e não há mais que n elementos na árvore, cada operação realizada na estrutura de dados do status da "fronteira de onda" é limitada a tempo O (log n).

Notamos que os eventos de círculo só podem ocorrer com três arcos consecutivos. Assim, em uma fila no máximo n sites lá nunca irá ocorrer mais do que n-2 eventos de círculo. Mais uma vez nossa fila tem n elementos, e assim cada uma das operações leva não mais que

tempo O(log n).

Porque há um número constante de eventos de site em Q e cada operação leva uma quantidade constante de tempo, vemos que o algoritmo de varredura de linha para determinar o diagrama de Voronoi em um conjunto de n pontos é executado em tempo de O (n log n).

Pseudo-código

Entrada: um conjunto P = (p1,p2,...pn) pontos no plano
Saida: O Diagrama de Voronoi Vor(P)

1. Inicialize uma fila de prioridade Q com eventos de site ordenados em ordem crescente pela coordenada x; inicialize uma estrutura de árvore balanceada vazia T 

2. Enquanto Q não estiver vazia

    (a) capture o próximo evento q fora de Q de menor coordenada Y
    (b) se q é um evento de site X:
          i. Se T estiver vazio, insira q em T e retorne, senão faça os passos ii a iv
          ii. Encontre o arco B que cruza a parábola X criada pela "fronteira de onda" e o site x

         iii. Insira uma nova parábola em T e divida a parábola (B) que está cortada em duas partes. Reequilibre T se necessário

         iv. Atualize Q pela deleção do evento de círculo que já não é alcançavel baseado no corte da "fronteira de onda" (ABC) e pela inserção dos três novos eventos de círculos possíveis criados pelo novo evento de site (A-B1-X, B1-X-B2, X-B2-C)

   (b) se q é um evento de círculo (x:ABxDE -> ABDE):
        i. Grave o Vértice de Voronoi
       ii. Delete o arco que desapareceu de T
      iii. Atualize Q devido a deleção de 3 novos eventos de círculos impossíveis (A-B-x, B-x-D, x-D-E) e insira os dois novos eventos de círculo possíveis A-B-D, B-D-E).

Diagrama de Voronoi

O Diagrama de Voronoi foi inventado para resolver um problema simples: Como dividir uma cidade em áreas irregulares de forma a que a área coberta por um carteiro vinculado a uma determinada agência de correio seja otimizada?

G. F. Voronoi, em sua tese de doutorado entitulada Sobre uma generalização do algoritmo de quebra de cadeias publicada em Varsóvia, Polônia, em 1896, desenvolveu um método onde, com base em uma triangulação pré-existente de pontos que representam os centros de alguma coisa (no caso da primeira aplicação, agências de correio), se determina qual a área de influência de cada um destes centros em função da posição dos outros centros, delimitando de forma geométrica cada área de influência.

O diagrama de Voronoi é um  método que muito útil para reconhecimento de padrões para delimitar as áreas de categorias ou classes em uma representação geométrica de suas distribuições.

Os “centros” são denominados de centróides. Se existe um conjunto de padrões constituído de um elemento típico para cada categoria que queremos representar (protótipo), pode-se  utilizar o diagrama de Voronoi para determinar a extensão de cada uma das categorias, apenas utilizando cada um dos protótipos como um centróide e gerando um diagrama de Voronoi sobre estes.

Para podermos gerar um diagrama de Voronoi partimos do conjunto de protótipos e geramos primeiramente uma triangulação. Para isto utilizamos o método da Triangulação de Delaunay, que veremos em detalhe adiante. Na figura 1, a triangulação está em vermelho.

Figura 1 - Triangulação de Delaunay

Realizada a triangulação, geramos as linhas que formarão as fronteiras das células do diagrama de Voronoi. Estas fronteiras são geradas por linhas perpendiculares ao ponto médio de cada aresta da triangulação produzida anteriormente. As intersecções destas perpendiculares formam os vértices das células do diagrama de Voronoi. Os segmentos de reta da perpendicular que se estendem para além de sua primeira intersecção com outra perpendicular nos dois sentidos são descartados.

Estruturas Geométricas:

Região de Voronoi 

• Vor(p)
• Coleção de pontos bidimensionais, onde todos os pontos estão mais perto do vértice p do que de qualquer outro vértice no grafo. 
• Diagrama de Voronoi é a união de todas as regiões de Voronoi do grafo
• Triangulação de Delaunay está relacionada com Diagrama de Voronoi
• Dois vértices p e q estão conectados em Del(V) apenas se Vor(p) e Vor(q) compartilham uma mesma borda

Triangulação de Delaunay

• Del(V)
• Assume que nenhum 4 vértices são co-circulares 
• Triangulação é de Delaunay se o circulo circunscrito de cada um de seus triângulos não contém outro vértice em seu interior

Passo-a-passo para criação do Diagrama de Voronoi.

Passo 1: Determinação dos pontos para os triângulos (Triangulação de Delaunay) 

Tome sua distribuição de dados e encontre todos os triângulos definidos por três pontos da distribuição, de tal forma que um círculo passando por estes três pontos não inclua nenhum outro ponto.

 Passo 1

Passo 2: Determinação dos triangulos (Triangulação de Delaunay)

Para cada conjunto de três pontos satisfazendo a condição de Delaunay encontrado, gere um triângulo.

Passo 2

Passo 3: Determinação das células (Diagrama de Voronoi)

P.3.1. Determine o ponto médio de cada uma das arestas do conjunto de triângulos gerado anteriormente. Considere cada aresta apenas uma vez.
P.3.2. Gere uma linha perpendicular a cada uma das arestas.
P.3.3. Determine as duas intersecções mais próximas de cada aresta com duas outras arestas. Um intersecção para cada lado. Ignore os segmentos de reta que seguem para além das intersecções.
P.3.4. Forme as células do diagrama com os polígonos formados por segmentos adjacentes. Ciclos geram células internas, polígonos abertos células externas.

Passo 3