Diagrama de Voronoi

Um diagrama de Voronoi divide o plano por um conjunto de pontos chamados geradores: a cada gerador pertence a região dos pontos que estão pelo menos tão perto dele como de qualquer outro gerador. A imagem é uma janela sobre o plano; o sombreado dentro de cada região serve apenas para a visualização. A sonda azul é o centro de um círculo vazio que chega ao gerador mais próximo. Aqui podes mover os geradores e ver as regiões vizinhas mudar, fazer crescer cada região a partir do seu gerador, ver a triangulação de Delaunay e distribuir os geradores mais uniformemente, aproximando-os de um favo de mel.

Os pontos que estão pelo menos tão perto de um gerador $p$ como de outro gerador $q$ formam um semiplano limitado pela mediatriz de $pq$. A região de $p$ é a interseção destes semiplanos, um por cada outro gerador, e por isso é convexa. Só algumas destas mediatrizes se tornam arestas. Os geradores cujas regiões partilham uma aresta com a de $p$ são os seus vizinhos; os restantes semiplanos já contêm toda a região. A moldura apenas delimita a janela. Uma região estende-se até ao infinito se e só se o seu gerador estiver na fronteira do invólucro convexo de todos os geradores.

Onde três ou mais regiões se encontram, o vértice está à mesma distância dos seus geradores, sendo por isso o centro de um círculo que passa por eles. No interior desse círculo não há nenhum gerador: se houvesse, estaria mais perto do vértice, que pertenceria à sua região. Normalmente, encontram-se exatamente três regiões num vértice. Encontram-se quatro quando exatamente quatro geradores estão sobre um círculo vazio, como numa grelha quadrada, algo que quase nunca acontece com geradores espalhados ao acaso.

Crescer faz crescer um disco a partir de cada gerador, todos à mesma velocidade. Cada ponto é alcançado primeiro pelo gerador mais próximo, pelo que as frentes se encontram exatamente nas arestas. A pequena vista mostra o mesmo crescimento de lado. Sobre cada ponto, coloca uma altura igual à distância ao gerador mais próximo: a menor altura entre os cones $z = |x - s|$ assentes nos geradores. As cristas são as arestas e o crescimento é água a subir. O último local inundado é o ponto mais alto da paisagem dentro da moldura, o centro do maior círculo vazio cujo centro está na moldura.

Triangulação une dois geradores sempre que as suas regiões partilham uma aresta e acrescenta diagonais tracejadas quando quatro ou mais geradores partilham um círculo vazio, como numa grelha quadrada. A menos que todos os geradores estejam alinhados, o resultado é a triangulação de Delaunay. A circunferência circunscrita de cada triângulo é a do círculo vazio em torno de um vértice do diagrama.

Uniformizar move cada gerador para o centroide da sua região recortada pela moldura e recalcula as regiões, iteração após iteração. É o algoritmo de Lloyd. O pequeno gráfico representa a distância quadrática média de um ponto da moldura ao gerador mais próximo, dividida pela área da moldura por gerador. Nenhuma iteração pode aumentá-la. Com os geradores fixos, as regiões do gerador mais próximo minimizam-na; com as regiões fixas, fazem-no os centroides. A linha do favo é um limite inferior: o valor para hexágonos regulares iguais com os geradores nos centros. Partindo de geradores dispersos, o processo para num estado estável próximo, não num favo perfeito. Normalmente ficam pentágonos e heptágonos lado a lado, como deslocações num cristal.

O diagrama deve o nome a Georgy Voronoy, que estudou estas divisões em qualquer dimensão em 1908; a triangulação deve-o a Boris Delaunay, que a descreveu em 1934.