# Algoritmos para construção do diagrama de Voronoi
## 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 $P$ = {$p_{1},p_{2},...,p_{n}$} contido em $R^{2}$, onde 2 ≤ n ≤ ∞ e $x_{i}$ ≠ $x_{j}$ para i, j pertencente a $I_{n}$ . Chamamos a região $V(p_{i})$ = ∩ $H(p_{i},p_{j}$).
O polígono de Voronoi ordinário associado com $p_{i}$ e o conjunto $V(P$) = {$V(p_{1}$), $V(p_{2}$), … , $V(p_{n})$} o diagrama de Voronoi ordinário plano gerados por $P$.

### Construção

Seja $P$ = {$p_{1},p_{2},...,p_{n}$} o conjunto de geradores, e $V$ = {$v_{1},v_{2},...,v_{n}$} denota o diagrama de Voronoi para $P$. A construção do diagrama é o procedimento para a geração $V(p)$. 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 $p_{i}$ gerador é a intersecção de todos os planos definidos por meio das meadiatrizes de $p_{i}$ 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 $p_{1},p_{2},...,p_{n}$.
* SAÍDA: Diagrama de Voronoi $V$ = {$V(p_{1}),V(p_{2})$}
      * Passo 1: Para cada i sendo i = 1,2, . . . , n, gerar n-1 planos intermediários $H(p_{1},p_{2})$ , 1 ≤ j ≤n, j ≠ i , e assim construir sua intersecção em comum $V(p_{i})$.
      * Passo 2: Retorna {$V(p_{1}),V(p_{2}),$ … ,$V(p_{n})$} 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 (p$_i$, p$_j$) para dois pontos dados p$_i$ e p$_j$ requer tempo constante. Assim, para cada p$_i$ o tempo necessário para a construção de um n-planos é proporcional a n-1, por exemplo $a(n-1)$, onde $a$ é 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 $1+2+...+n-2=(n-2)*(n-1)/2$, dizem $b*(n-2)(n-1)$ em que $b$ é uma outra constante positiva. Temos que repetir esse processo para todos os geradores, e, consequentemente, o tempo total exigido pelo método ingênuo é:
$T(n)=n{a(n-1)+b(n-2)(n-1)}=O(n^{3})$
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 $O(nlogn)$. Por isso, a complexidade de tempo do método naive pode ser reduzida para $O(n^{2}nlog)$
Existem outros algoritmos para construção do diagrama de Voronoi que requerem pelo menos $O(nlogn)$ no pior caso, e pelo menos $O(n)$, 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 P$_1$, P$_2$, P$_3$ e P$_4$ 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 P$_1$ 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.