Diagrama de Voronoy
O Diagrama de Voronoi é uma técnica matemática que decompõe um espaço, como um espaço métrico, em regiões ou 'células' com base na proximidade a um conjunto de objetos, chamados 'sítios' ou 'geradores'. Cada célula de Voronoi agrupa todos os pontos do espaço que estão mais próximos de um determinado sítio do que de qualquer outro. Também conhecido como Tesselação de Voronoi, Decomposição de Voronoi ou Mosaico de Dirichlet, o conceito foi nomeado em homenagem a Georgy Voronoi. Sua versatilidade o torna útil em diversas áreas da ciência, tecnologia e até na arte, com inúmeras aplicações práticas e teóricas.
Pontos-chave
- Decompõe um espaço em células baseadas na proximidade a 'sítios' ou 'geradores'.
- Cada célula de Voronoi contém pontos mais próximos de um sítio específico.
- Nomeado em homenagem ao matemático Georgy Voronoi, também conhecido como Mosaico de Dirichlet.
- As células são definidas pela distância dos pontos aos sítios.
- Possui vasta aplicação em ciência, tecnologia e arte.
Imagem: Thomazthz · BY-SA · Openverse
No cenário mais comum e intuitivo, consideramos um conjunto finito de pontos {p1,...,pn} no Plano Euclidiano. Aqui, cada sítio pk é um ponto simples, e sua célula de Voronoi correspondente (também chamada de região Voronoi ou célula de Dirichlet) Rk é o conjunto de todos os pontos no plano que estão mais próximos de pk do que de qualquer outro sítio. Essas células são polígonos convexos, formados pela interseção de semiespaços. Os segmentos que compõem o diagrama de Voronoi são os pontos equidistantes de dois sítios mais próximos, enquanto os vértices (ou nós) de Voronoi são os pontos equidistantes de três ou mais sítios.
Imagem: Thomazthz · BY-SA · Openverse
Formalmente, seja X um espaço não vazio com uma função de distância d. Considere K um conjunto de índices e (Pk)k ∈ K uma tupla de subconjuntos não vazios (os sítios) em X. A célula de Voronoi Rk, associada ao sítio Pk, é o conjunto de todos os pontos em X cuja distância a Pk não é maior que a distância a qualquer outro sítio Pj (onde j ≠ k). Se d(x,A) = inf{d(x,a): a ∈ A} denota a distância entre um ponto x e um subconjunto A, então Rk = {x ∈ X: d(x,Pk) ≤ d(x,Pj) para todo j≠k}. O Diagrama de Voronoi é a tupla dessas células (Rk)k ∈ K. Embora sítios possam se cruzar ou coincidir (como no exemplo de lojas), geralmente são considerados disjuntos. Sítios infinitos também são permitidos, com aplicações em geometria dos números e cristalografia, mas frequentemente o foco é em um número finito de sítios.
Imagem: Thomazthz · BY-SA · Openverse
Para ilustrar, imagine um grupo de lojas em uma cidade plana. Se quisermos estimar o número de clientes de uma loja específica, podemos assumir que os clientes escolhem a loja mais próxima, considerando que outros fatores (preço, produtos, qualidade) são iguais. Nesse cenário, a célula de Voronoi Rk de uma loja Pk pode ser usada para estimar o número de potenciais clientes que a frequentariam. A distância padrão, ou Euclidiana, d((a1,a2),(b1,b2))=((a1-b1)²+(a2-b2)²)⁰,⁵, é comumente usada. No entanto, em cidades como Manhattan, onde o tráfego segue eixos x e y, a distância l1 (ou Manhattan), d((a1,a2),(b1,b2))=|a1-b1|+|a2-b2|, seria uma medida mais realista para o deslocamento dos clientes.
Imagem: Thomazthz · BY-SA · Openverse
O uso informal de Diagramas de Voronoi remonta a Descartes em 1644. Dirichlet aplicou diagramas 2D e 3D em seus estudos de formas quadráticas em 1850. Em 1854, o médico John Snow usou um diagrama de Voronoi para mapear a epidemia de cólera, mostrando que a maioria das vítimas vivia mais perto da bomba de água da Broad Street. O nome 'Diagrama de Voronoi' foi dado em homenagem ao matemático russo Georgy Fedoseevich Voronoi, que definiu e estudou o caso n-dimensional geral em 1908. Em geofísica e meteorologia, para análise de dados espacialmente distribuídos (como medições de chuva), são chamados de Polígonos de Thiessen, devido aos estudos de Alfred H. Thiessen. Na física da matéria condensada, são conhecidos como células unitárias de Wigner-Seitz, e na rede recíproca de momentos, como zonas de Brillouin. Para reticulados gerais em grupos de Lie, são chamados de domínios fundamentais, e em espaços métricos, de polígonos métricos fundamentais.
Imagem: Thomazthz · BY-SA · Openverse
Diagramas de Voronoi gerados a partir de reticulados regulares de pontos em duas ou três dimensões produzem muitos padrões familiares. Por exemplo, para um conjunto de pontos (x, y) onde x pertence a um conjunto discreto X e y a um conjunto discreto Y, resultam em telhas retangulares, onde os pontos geradores não estão necessariamente no centro das células.
Enquanto uma célula de Voronoi comum é definida como o conjunto de pontos mais próximo de um único ponto em S, as células de Voronoi de enésima ordem são definidas como o conjunto de pontos que têm um determinado conjunto de n pontos em S como seus n vizinhos mais próximos. Esses diagramas também subdividem o espaço e podem ser gerados recursivamente. Para criar um Diagrama de Voronoi de enésima ordem de um conjunto S, começa-se com o diagrama de ordem (n-1) e substitui-se cada célula gerada por X = {x1, x2, ..., xn-1} pelo Diagrama de Voronoi gerado a partir do conjunto S - X.
Diagrama de Voronoi do Ponto Mais Distante
Para um conjunto de n pontos, o Diagrama de Voronoi de ordem (n-1) é chamado de Diagrama de Voronoi do Ponto Mais Distante. Para um dado conjunto S = {p1, p2, ..., pn}, ele divide o plano em células onde o mesmo ponto de P é o ponto mais distante. Um ponto de P tem uma célula neste diagrama se e somente se for um vértice do fecho convexo de P. Assim, se H = {h1, h2, ..., hk} é o fecho convexo de P, o Diagrama de Voronoi do Ponto Mais Distante é a subdivisão do plano em k células, uma para cada ponto em H. Um ponto q está na célula correspondente a hi se e somente se dist(q, hi) > dist(q, pj) para cada pj∈S com hi ≠ pj, onde dist(p, q) é a distância euclidiana entre p e q.
A definição de células de Voronoi permite o uso de métricas de distância não-euclidianas, como Mahalanobis ou Manhattan. No entanto, nesses casos, os limites das células podem ser mais complexos, pois o lugar geométrico equidistante de dois pontos pode não ser um subespaço de co-dimensão 1, mesmo em 2D. O Diagrama de Voronoi Ponderado atribui pesos aos pontos geradores, modificando a função de distância. Diferente das células Voronoi padrão, algumas células ponderadas podem ser vazias. O espaço de armazenamento necessário para um Diagrama de Voronoi de n pontos em um espaço d-dimensional é da ordem de O(n^(⌈d/2⌉)). Isso torna os Diagramas de Voronoi inviáveis para d > 2 em muitos casos, levando ao uso de aproximações onde as fronteiras das células são difusas.
