Algoritmo Naive

O algoritmo naive ou ingênuo para a construção do diagrama de Voronoi é o método mais simples e fácil de se ser provado, porém ineficiente, a partir disso, foram realizadas muitas pesquisas no campo da geometria computacional para fazer algoritmos eficientes.

Definição

Dado um conjunto de dois ou mais, mas um número finito, de pontos distintos no espaço euclidiano, associamos todos os locais em que o espaço com o membro mais próximo(s) do ponto de ajuste em relação ao distância euclidiana. O resultado é uma camada do plano em um conjunto de regiões associadas com os membros de um conjunto de pontos. Chamamos isso de diagrama de Voronoi ordinário planar gerado pelo conjunto de pontos, e as regiões que constituem o diagrama de Voronoi de polígonos de Voronoi ordinários.

Seja = {} contido em , onde 2 ≤ n ≤ ∞ e ≠ para i, j pertencente a . Chamamos a região = ∩ ).

O polígono de Voronoi ordinário associado com e o conjunto ) = {), ), … , } o diagrama de Voronoi ordinário plano gerados por .

Construção

Seja = {} o conjunto de geradores, e = {} denota o diagrama de Voronoi para . A construção do diagrama é o procedimento para a geração . A partir da definição que vimos do Diagrama de Voronoi ordinario a partir de meios planos é possível criar um método ingénuo para a construação do diagrama.

O polígono de Voronoi para o gerador é a intersecção de todos os planos definidos por meio das meadiatrizes de e dos outros geradores. Assim podemos construir os polígonos de Voronoi um por um que serão no final o Diagrama de Voronoi a partir do seguinte método:

Algoritmo

Método Naive:

VORONOI_DIAGRAM

ENTRADA: n geradores . SAÍDA: Diagrama de Voronoi = {}

Passo 1: Para cada i sendo i = 1,2, . . . , n, gerar n-1 planos intermediários , 1 ≤ j ≤n, j ≠ i , e assim construir sua intersecção em comum .

Passo 2: Retorna { … ,} todas as intersecções a partir dos geradores.

Avaliação do método naive

O método naive não pode ser chamado de 'algoritmo' prático, porque é "insuficiente".

Para avaliar um algoritmo, temos que considerar pelo menos se ele é correto e sua eficiência, e se se tratando de computação numérica, nós também temos que considerar robustez contra erros numéricos. O método acima é correto, porque é uma atualização da definição do diagrama de Voronoi. Assim, consideramos os outros dois aspetos.

Eficiência do método naive

Primeiro vamos avaliar a eficiência. Para construção de um plano intermediário H (pi, pj) para dois pontos dados pi e pj requer tempo constante. Assim, para cada pi o tempo necessário para a construção de um n-planos é proporcional a n-1, por exemplo , onde é uma constante positiva. Para construir a intersecção dos planos, vamos considerar o seguinte procedimento:

Primeiro, construir a interseção de dois planos, obtendo um polígono com dois lados.

Depois construir a interseção deste polígono com o terceiro plano.

Na k-ésima etapa deste procedimento, temos que encontrar a interseção de um polígono k lados (no pior dos casos) com outro plano, e o tempo desta etapa é pelo menos proporcional ao k, se verificarmos se cada um dos lados de k cruza a linha limite do plano. Esta construção da intersecção dos planos n-1 requer tempo proporcional a , dizem em que é uma outra constante positiva. Temos que repetir esse processo para todos os geradores, e, consequentemente, o tempo total exigido pelo método ingênuo é:

.

Isto significa que, para um programa de computador com base no procedimento acima, o tempo para o processamento torna-se oito vezes maior do que o tamanho da entrada e torna-se o dobro do tamanho.

Empregando uma técnica pouco mais sofisticada, podemos construir a interseção de n-1 planos em . Por isso, a complexidade de tempo do método naive pode ser reduzida para

Existem outros algoritmos para construção do diagrama de Voronoi que requerem pelo menos no pior caso, e pelo menos , em média. Além disso, existem algoritmos cuja complexidade de tempo atinge estes limites, e alguns deles, na verdade, tem tempo de execução muito curto, mesmo para pequenos valores de n (embora a própria ordem representa o comportamento do algoritmo que n se aproxima do infinito). Em comparação com estes algoritmos, o algoritmo naive não é muito satisfatório do ponto de vista de complexidade de tempo.

Robustez do método naive Outro ponto de suma importância de vista para avaliar o algoritmo é a robustez contra erros numéricos. Sob este ponto de vista também o método naive não é satisfatório. Isso pode ser entendido através do seguinte exemplo: Suponha-se que há apenas quatro geradores P1, P2, P3 e P4 e eles estão muito próximos de um círculo em comum. Então as três bissetrizes entre p1 e os outros mais próximos geradores passam para o centro do círculo. Se o erro numérico ocorre, é difícil decidir as posições relativas dos pontos de interseção dessas mediatrizes. Por isso, o resultado da intersecção dos três planos associados a P1 pode ser um polígono de dois lados ou um polígono de três lado, dependendo o número de erros numéricos. Os outros três polígonos de Voronoi têm instabilidade similar. No método naive, cada polígono de Voronoi é calculado de forma independente, de modo que o resultado poderá tornar-se inconsistente topologicamente. De um ponto de vista teórico, todos os polígonos de Voronoi um mosaico dos planos, mas no cálculo real a saída do método naive, não proporciona necessariamente um mosaico dos planos. Assim, o método naive, se traduzido para um programa de computador de uma maneira simples, não é robusto contra erros numéricos. Sua produção pode ser inconsistente topologicamente. Precisamos de uma análise cuidadosa, a fim de fazer um algoritmo numericamente robusto. O método naive, apresentado acima, é um dos métodos mais fáceis de compreender, porque é uma tradução direta da definição do diagrama de Voronoi. Este método não é recomendado para propósitos gerais, ele pode ser usado para alguns tipos especiais de simulação onde o objetivo não é construir o próprio diagrama de Voronoi, mas para gerar muitas amostras de polígonos de Voronoi para obter dados estatísticos, tais como a distribuição do número de arestas por polígono. Portanto a saída do método ingênuo é uma coleção de polígonos de Voronoi, e ele não inclui informações explícitas sobre a estrutura topológica do diagrama. Para extrairmos vários tipos de informação a partir do diagrama de Voronoi, o método ingênuo não é adequado.

Bibliografia

Algoritmos para a construção de Diagramas de Voronoi

Algoritmo Incremental

O algoritmo incremental para a construção de diagramas de Voronoi foi proposto por Peter Green e Robin Sibson em 1978. Este algoritmo gasta tempo para cada inserção de ponto, para uma complexidade total de . Apesar de ter complexidade quadrática, é um método simples e popular para a construção de diagramas de Voronoi.

Descrição

Este algoritmo começa com um Diagrama de Voronoi para um dado conjunto de pontos . Novas arestas são construídas à medida que novos pontos são adicionados. A ideia básica é construir um polígono de Voronoi para um novo ponto que é adicionado ao conjunto de pontos . As etapas do algoritmo estão descrito a seguir :

thumb|Etapas do algoritmo incremental.

A) O primeiro passo é identificar o ponto cujo polígono de Voronoi contém o ponto . B) Construa uma mediatriz do segmento o qual interceta o em e , respectivamente. C) Assumindo que é orientado no sentido anti-horário, adicione uma mediatriz do segmento no polígono de Voronoi adjacente ao ponto . D) Os passos B e C são repetidos até que o ponto for revisitado. E) Neste ponto, o polígono de Voronoi para o ponto é obtido. F) O novo Diagrama de Voronoi é obtido pela remoção da subestrutura dentro do polígono de Voronoi para .

thumb|Exemplo do algoritmo incremental.

Exemplo Seja o conjunto de pontos , e . Se um ponto é adicionado ao conjunto, deve ser escolhido como o ponto inicial para a construção do novo diagrama de Voronoi (DV), uma vez que o polígono de Voronoi que contém contém e é o mais próximo deste último. Uma mediatriz que corta o segmento é adicionada, a qual intercepta o DV nos pontos e . Similarmente, mediatrizes que cortam e são desenhadas as quais interceptam o polígono de Voronoi de em e , e aquele de em e . O novo DV é obtido removendo a subestrutura interna do novo polígono de Voronoi formado.

Divisão e conquista O primeiro algoritmo a utilizar o paradigma computacional da divisão e conquista para construção de Diagramas de Voronoi, foi proposto por Shamos e Hoey em 1975. Foi também o primeiro algoritmo a computador os diagramas com complexidade no pior dos casos.

Descrição O algoritmo considera um conjunto de pontos divididos em dois subconjuntos e , cada um contendo pontos, de tal modo que cada ponto de encontra-se à esquerda de qualquer ponto de .

Assumindo que já possuímos os diagramas de Voronoi e , construídos recursivamente, a etapa de união dos diagramas é realizada traçando-se uma reta poligonal , também conhecida como cadeia divisória, que divide ambos conjuntos de pontos verticalmente. Essa cadeia possui a propriedade de que cada reta horizontal intersecta exatamente em um único ponto, uma vez que toda linha poligonal que separa dois conjuntos disjuntos em x é monótona em y.

A cadeia faz um percurso sobre o lugar geométrico equidistante de algum ponto de e algum ponto de . Basicamente, o caminho percorrido acaba formando segmentos de reta pertencentes a uma fronteira comum de uma região de um certo ponto de , com a região um certo ponto de . Visto isso, forma as novas arestas do diagrama de Voronoi dado por. .

Após a construção de , a união está praticamente concluída, sendo necessário apenas eliminar parte das arestas de e que cruzam .

Como computar a cadeia divisória

A essência do algoritmo está na construção da reta poligonal . Podemos computa-la através dos seguintes passos: Computar o fecho convexo de e o fecho convexo de . Encontrar o par de pontos, e que define a ponte superior de junção dos fechos convexos de e Criar uma aresta consistindo da mediatriz desses dois pontos, a partir do , e definir como aresta atual. Sempre que a aresta atual encontrar uma aresta existente, muda-se um dos dois pontos. Se a aresta encontrada pertence à , então atualiza-se o ponto , caso contrário atualiza-se o ponto . O ponto é trocado pelo outro ponto equidistante da aresta que foi interceptada. Criar uma nova aresta a partir sobre a mediatriz desses novos pontos que passa a ser a reta atual. Adicionar essa aresta à Repetir passos 4, 5 e 6 até que a ponte inferior de junção dos fechos convexos seja alcançada.

Pseudocódigo

VORONOI_DIAGRAM

ENTRADA: Uma lista/conjunto S = {s1, s2,..., sn} de pontos em ordem ascendente em relação a coordenada x, onde n > 3

SAÍDA: Diagrama de Voronoi V(S)

Seja t a parte inteira de n/2, dividir S em SE = {s1, s2,..., st} e SD = {st+1, st+2,..., sn} Construir o Diagrama de Voronoi V(SE) de SE recursivamente Construir o Diagrama de Voronoi V(SD) de SD recursivamente Combinar V(SE) e V(SD) em V(S) i.e, V(S)=V(SE) ∪ V(SD) computando a cadeia divisória e podando as arestas desnecessárias. Devolve V(S)

Algoritmo de Fortune

Para a construção de diagramas de Vornoi, o Algoritmo de varredura (Sweep Algorithm) foi proposto em 1986 por Steven Fortune através do artigo "A Sweepline Algorithm for Voronoi Diagrams" (Tradução livre: Um algoritmo de linha de varredura para os diagramas de Voronoi). Esse algoritmo é normalmente chamado de Algoritmo de Fortune, em referência a seu autor, tem complexidade e é, portanto, considerado um algoritmo ótimo para a construção dos diagramas.

Descrição

Inicialmente temos um conjunto de pontos dispostos no plano Em seguida, criamos um conjunto de cones idênticos, de forma que, para cada ponto do conjunto haja um cone que cresce em direção ao eixo .