Diagrama de Voronoy

Diagrama de Voronoi de um conjunto aleatório de pontos no plano (todos os pontos estão contidos na imagem).

Na matemática, um Diagrama de Voronoi é um tipo especial de decomposição de um dado espaço, por exemplo, um espaço métrico, determinado pela distância para uma determinada família de objetos (subconjuntos) no espaço. Estes objetos são normalmente chamados de sítios ou geradores (apesar de nomes como “sementes” estarem também em uso). Cada sítio está associado a célula de Voronoi correspondente, isto é um conjunto de todos os pontos no dado espaço o qual a distância para o dado sítio não é maior que sua distância para os outros objetos. Foi nomeado de Georgy Voronoi posteriormente, e também chamado de Tesselação de Voronoi, uma Decomposição Voronoi, ou um Mosaico de Dirichlet (em homenagem a Lejeune Dirichlet). Diagramas de Voronoi podem ser encontrados em diversos campos da ciência e tecnologia, até mesmo na arte, tendo inúmeras aplicações práticas e teóricas.

Caso Base

No caso base e nos casos mais familiares (mostrados na primeira figura), temos um conjunto finito de pontos {p₁,...,p_n} no Plano Euclidiano. Neste caso cada sítio p_k é meramente um ponto, e corresponde a uma célula Voronoi (também chamada de região Voronoi ou célula Dirichlet) R_k consistindo em todos os pontos que possuem distância para p_k menor do que a distância para qualquer outro sítio. Cada célula é obtida a partir da interseção de semiespaços e, portanto, é um polígono convexo. Os segmentos do diagrama de Voronoi são todos os pontos do plano equidistantes aos dois sítios mais próximos. Os vértices (nós) de Voronoi são os pontos equidistantes de três ou mais sítios.

Definição Formal

Seja X um espaço (um conjunto não vazio) terminado com uma função distância d. Seja K um conjunto de índices e (P_k)_{k ∈ K} sendo uma tupla (coleção ordenada) de subconjuntos não vazios (os sítios) no espaço X. A célula Voronoi, ou região Voronoi, R_k, associada ao sítio P_k é o conjunto de todos os pontos em X os quais a distância para P_k não é maior do que a distância para os outros sítios P_j , onde j é qualquer índice diferente de k. Em outras palavras, se d(x,A)=inf{d(x,a): a in A} denota a distância entre o ponto x e o subconjunto A, então R_k={x in X: d(x,P_k) ≤ d(x,P_j) for all j≠k}. O Diagrama de Voronoi é simplesmente a tupla de células (R_k)_{k ∈ K} . A princípio, alguns dos sítios podem se cruzar e até coincidir (uma aplicação é descrita abaixo para os sítios que representam lojas), mas normalmente assume-se que são disjuntos. Além disso, sítios infinitos são permitidos na definição (esta definição tem aplicações na geometria dos números e cristalografia), mas, novamente, em muitos casos apenas finitamente alguns sítios são considerados.

No caso particular onde o espaço é um espaço euclidiano de dimensão finita, cada sítio é um ponto, há um número finito de pontos e todos eles são diferentes, então as células Voronoi são politopos convexos que podem ser representados de uma forma combinatória utilizando seus vértices, os lados, faces 2-dimensional, etc. Às vezes a estrutura combinatória induzida é referida como o Diagrama de Voronoi. No entanto, em geral, as células de Voronoi podem não ser convexas ou mesmo não estar conectadas.

Ilustração

Como uma ilustração simples, considere um grupo de lojas em uma cidade plana. Suponha que queiramos estimar o número de clientes de uma determinada loja. Com todo o resto sendo igual (preço, produtos, qualidade de serviço, etc), é razoável supor que os clientes escolhem sua loja preferida, simplesmente por considerações de distância: eles vão para a loja com localização mais próxima a eles. Neste caso, a célula R_k de Voronoi de uma determinada loja de P_k pode ser utilizado para dar uma estimativa aproximada do número de potenciais clientes indo a esta loja (que é modelada por um ponto em nossa cidade plana).

Até agora pensava-se que a distância entre os pontos da cidade eram medidos utilizando-se a distância standard, ou seja, a distância Euclidiana: d((a₁,a₂),(b₁,b₂))=((a₁-b₁)²+(a₂-b₂)²)^0.5. No entanto, se considerarmos o caso em que os clientes só vão para as lojas por um veículo e os caminhos de tráfego são paralelos aos eixos x e y, como na ilha de Manhattan, em seguida, uma função de distância mais realista será a distância l₁, ou seja, d((a₁,a₂),(b₁,b₂))=|a₁-b₁|+|a₂-b₂|.

Propriedades

• O grafo dual para um Diagrama de Voronoi (no caso de um espaço Euclideano com pontos em sítios) corresponde a Triangulação de Delaunay para o mesmo conjunto de pontos.
• O par de pontos mais próximo corresponde a duas células adjacentes do Diagrama de Voronoi.
• Assuma um cenário onde o plano Euclideano e um grupo de diferentes pontos são dados. Então, dois pontos são adjacentes no fecho convexo se e somente se suas células Voronoi compartilham um lado infinitamente longo.
• Se o espaço é normalizado e a distância para cada local é atingido (por exemplo, quando um site é um conjunto compacto ou uma bola fechada), então cada célula de Voronoi pode ser representada como uma união de segmentos de linha que emana dos sítios. Como mostrado lá, esta propriedade não é necessariamente válida quando a distância não é atingida.
• Em condições relativamente gerais (o espaço é possivelmente um espaço dimensional infinito uniformemente convexo, podendo haver um número infinito de sítios de uma forma geral etc.). As células Voronoi desfrutam de um propriedade com certa estabilidade: uma pequena mudança nas formas dos sítios, por exemplo, uma mudança causada por alguma tradução ou distorção, produz uma pequena mudança na forma das células Voronoi. Esta é a estabilidade geométrica dos Diagramas de Voronoi. Como mostrado lá, esta propriedade não se sustenta em geral, mesmo se o espaço é bidimensional (mas não uniformemente convexo, e, em particular, não euclidianos) e os sítios são pontos.

História

Uso informal de Diagramas de Voronoi têm como primeiro registro em 1644, por Descartes em 1644. Dirichlet utilizou 2-dimensional e diagramas 3-dimensional Voronoi em seu estudo sobre formas quadráticas em 1850. O médico britânico John Snow utilizou também um diagrama de Voronoi, em 1854, para ilustrar como a maioria das pessoas que morreram na epidemia de cólera vivia mais perto da bomba de água de Broad Street do que de qualquer outra bomba.

Diagrama de Voronoi foi nomeado após o matemático russo Georgy Fedoseevich Voronoi (ou Voronoy) definir e estudar o caso n-dimensional geral, em 1908. Diagramas de Voronoi que são utilizados em geofísica e meteorologia para analisar os dados espacialmente distribuídos (tais como as medições de chuva) são chamados polígonos de Thiessen graças aos estudos de aplicação do meteorologista americano Alfred H. Thiessen. Em física da material condensada, como pavimentações, os diagramas são conhecidos como células unitárias de Wigner-Seitz. Diagramas de Voronoi da rede recíproca dos momentos são chamados de zonas de Brillouin. Para reticulados gerais em grupos de Lie, as células são simplesmente chamadas de domínios fundamentais. No caso de espaços métricos as células são frequentemente chamadas de polígonos métricos fundamentais.

Exemplos

Este é um pedaço do diagrama de Voronoi de um conjunto aleatório de pontos em uma caixa 3D. Em geral, uma seção transversal de um diagrma de Voronoi 3D não é um diagrama de Voronoi em 2D em si. (todas as células são Poliedros Convexos.)

Diagramas de Voronoi de reticulados regulares de pontos em duas ou três dimensões dão origem a muitos diagramas familiares.

• O reticulado 2D nos dá um diagrama de favo de mel irregular, com hexágonos iguais e pontos simétricos; no caso de uma rede triangular, é regular; no caso de uma rede retangular, os hexágonos são reduzidos à retângulos em linhas e colunas; uma rede quadrada nos dá um diagrama regular em forma de mosaico; note que os retângulos e os quadrados também podem ser gerados por outras redes (por exemplo, a rede definida pelos vetores (1,0) e (1/2,1/2) produz quadrados). Veja aqui um exemplo visual dinâmico.
• Uma rede cúbica 3D produz um favo de mel cúbico.
• Planos paralelos com redes triangulares regulares alinhadas, com cada um alinhado com o centro dos outros, produz um favo de mel prismático hexagonal.
• Certos corpos centrados reticulados tetragonais produzem um diagrama do espaço com dodecaedro rhombo-hexagonal.
• Um reticulado cúbico face-centrado produz um diagrama do espaço com dodecaedro r-hombic.
• Um reticulado cúbico corpo-centrado produz um diagrama do espaço com octaedros truncados.

Para o conjunto de pontos (x, y) com x em um conjunto discreto X e y em um conjunto discreto Y, temos telhas retangulares com os pontos não necessariamente em seus centros.

Diagramas de Voronoi de Ordem Superior

Apesar de uma célula de Voronoi normal ser definida como o conjunto de pontos mais próximo de um único ponto em S, a enésima ordem de células de Voronoi é definida como o conjunto de pontos com um determinado conjunto de n pontos em S contendo os vizinhos mais próximos de n. Diagramas de Voronoi de Ordem Superior também subdividem o espaço. Diagramas de Voronoi de Ordem Superior podem ser gerados de forma recursiva. Para gerar o Diagrama de Voronoi da enésima ordem do conjuntoS, comece com o diagrama da ordem (n − 1)^th- e substitua cada célula gerada por X = {x₁, x₂, ..., x_n−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 de Ponto mais Distante.

Para um dado conjunto de pontos S = {p₁, p₂, ..., p_n} o Diagrama de Voronoi de Ponto mais Distante divide o plano em células onde o mesmo ponto de P é o ponto mais distante. Note que o ponto de P possui uma célula no Diagrama de Voronoi de Ponto mais Distante se e somente se este for um vértice do fecho convexo de P. Portanto, seja H = {h₁, h₂, ..., h_k} o fecho convexo de P':' definimos o Diagrama de Voronoi de Ponto mais distante como a subdivisão do plano em k células,uma para cada ponto em H, com a propriedade de que um ponto q que está na célula correspondente a um sítio hi se e somente se dist(q, h_i) > dist(q, p_j) para cada pj∈S com hi ≠ pj, onde dist(p, q) é a distância euclidiana entre dois pontos p e q.

Generalizações e Variações

Como implica a definição, as células de Voronoi podem ser definidas para métricas de distâncias não-euclidianas (como a Mahalanobis ou Manhattan). Entretanto, nestes casos, os limites das células de Voronoi podem ser mais complexos do que nos casos Euclidianos, uma vez que o lócus equidistante de dois pontos pode não ser um subespaço de co-dimensão 1, mesmo no caso 2-dimensional. Um Diagrama de Voronoi Ponderado é aquele em que a função de um par de pontos para definir uma célula Voronoi é uma função distância modificada por atribuição de pesos aos pontos geradores. Diferentemente do caso das células Voronoi definidas pela distância métrica, neste caso, algumas células Voronoi podem ser vazias.

O Diagrama de Voronoi de n pontos em um espaço d-dimensional requer espaço de armazenamento da ordem de$O(n^{\lceil d/2\rceil })$. Portanto, Diagramas de Voronoi muitas vezes não são viáveis para d > 2. Uma alternativa é utilizar aproximação do Diagrama de Voronoi, onde as células de Voronoi têm uma fronteira difusa, podendo ser aproximada.

Diagramas de Voronoi também estão relacionados com outras estruturas geométricas como o eixo medial (que tem encontrado aplicações em segmentação de imagens, reconhecimento óptico de caracteres e outras aplicações computacionais) e o Esqueleto Reto.

Aplicações

• Uma das primeiras aplicações do Diagrama de Voronoi foi por John Snow para estudar a epidemia de cólera no bairro londrino do Soho em 1854, localizado na Inglaterra. Ele mostrou a correlação entre áreas do mapa de Londres e as áreas com mais mortes devido ao surto, utilizando uma bomba de água particular.

• Uma estrutura de dados de localização de pontos pode ser construída através do Diagrama de Voronoi, a fim de responder a questões como o vizinho mais próximo ou o objeto que está mais próximo de um ponto de determinada consulta. Consultas a vizinho mais próximo têm inúmeras aplicações. Por exemplo, encontrar o hospital mais próximo ou o objeto mais similar em um banco de dados. Uma aplicação importante é a quantização vetorial, comumente utilizada em compressão de dados.

• Com um determinado Diagrama de Voronoi, pode-se também encontrar o maior círculo vazio dentre um conjunto de pontos em um polígono abrangente; por exemplo, para construir um novo supermercado o mais distante possível dos demais supermercados existentes, em uma determinada cidade plana.

• Diagramas de Voronoi juntamente com Diagramas de Voronoi de Ponto mais Distante são utilizados em algoritmos eficientes para calcular o arredondamento de pontos.

• Diagrama de Voronoi é útil em física de polímeros. Pode ser utilizado na representação do volume livre do polímero.

• Também é utilizado em derivações da capacidade de uma rede sem fio.

• Em Climatologia, Diagramas de Voronoi são utilizados para calcular a precipitação de uma área, com base em uma série de medições pontuais. Neste caso, geralmente referenciados como polígonos Thiessen.

• Diagramas de Voronoi são utilizados para estudar os padrões de crescimento das florestas. Também pode ser útil no desenvolvimento de modelos preditivos para incêndios florestais.

• Diagramas de Voronoi também são utilizados em computação gráfica para gerar alguns tipos de texturas orgânicas.

• Em robótica autônoma de navegação, Diagramas de Voronoi são utilizados para encontrar rotas livres. Se cada obstáculo do percurso for representado por um ponto, então as bordas do diagrama serão as rotas mais distantes dos obstáculos (afastando assim, em teoria, o risco de colisões).

• Em química computacional, as células Voronoi definidas pelas posições dos núcleos em uma molécula são usadas para calcular cargas atômicas. Isto é feito utilizando o método de densidade de deformação de Voronoi.
• Na ciência dos materiais, microestruturas policristalinas em ligas metálicas são geralmente representadas utilizando Diagramas de Voronoi.

• Polígonos de Voronoi têm sido utilizados na mineração, para estimas as reservas de materiais valiosos, minerais e outros recursos. Os pontos onde já ocorre a exploração são utilizados como o conjunto de pontos nos polígonos de Voronoi.

Ver também

Algoritmos

• Bowyer–Watson -- an algorithm for generating a Voronoi diagram in any number of dimensions.
• Fortune's algorithm -- an O(n log(n)) algorithm for generating a Voronoi diagram from a set of points in a plane.
• Lloyd's algorithm

Related subjects

• Centroidal Voronoi tessellation
• Computational geometry
• Triangulação de Delaunay
• Diagrama matemático
• Nearest neighbor search
• Nearest-neighbor interpolation
• Pole

Bibliografia

• Gustav Lejeune Dirichlet (1850). Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. Journal für die Reine und Angewandte Mathematik, 40:209-227.
• «Nouvelles applications des paramètres continus à la théorie des formes quadratiques». Journal für die Reine und Angewandte Mathematik. 133: 97-178. 1908. doi:10.1515/crll.1908.133.97 
• Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations - Concepts and Applications of Voronoi Diagrams. 2nd edition. John Wiley, 2000, 671 pages ISBN 0-471-98635-6
• Aurenhammer, Franz (1991). «Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure». ACM Computing Surveys. 23 (3): 345-405. doi:10.1145/116873.116880 
• Bowyer, Adrian (1981). «Computing Dirichlet tessellations». The Computer Journal. 24 (2): 162-166. doi:10.1093/comjnl/24.2.162 
• Reem, Daniel (2009). «An algorithm for computing Voronoi diagrams of general generators in general normed spaces». Proceedings of the sixth International Symposium on Voronoi Diagrams in science and engineering (ISVD 2009): 144—152. doi:10.1109/ISVD.2009.23 
• Daniel Reem (2011). The geometric stability of Voronoi diagrams with respect to small changes of the sites. Full version: arXiv 1103.4125 (2011), Extended abstract: in Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG ‏2011), pp. 254-263.
• Watson, David F. (1981). «Computing the n-dimensional tessellation with application to Voronoi polytopes». The Computer Journal. 24 (2): 167-172. doi:10.1093/comjnl/24.2.167 
• Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry 2nd revised edition ed. [S.l.]: Springer-Verlag. ISBN 3-540-65620-0  !CS1 manut: Nomes múltiplos: lista de autores (link) Chapter 7: Voronoi Diagrams: pp. 147–163. Includes a description of Fortune's algorithm.
• Rolf Klein (1989). Abstract voronoi diagrams and their applications. Col: Lecture Notes in Computer Science. 333. [S.l.]: Springer-Verlag. pp. 148—157. ISBN 3540520554. doi:10.1007/3-540-50335-8_31 

Ligações externas

• Real time interactive Voronoi / Delaunay diagrams with draggable points, Java 1.0.2, 1996-1997
• Real time interactive Voronoi and Delaunay diagrams with source code
• Demo for various metrics
• Mathworld on Voronoi diagrams