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.