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.[1][2]

Caso Base[editar | editar código-fonte]

No caso base e nos casos mais familiares (mostrados na primeira figura), temos um conjunto finito de pontos {p1,...,pn} no Plano Euclidiano. Neste caso cada sítio pk é meramente um ponto, e corresponde a uma célula Voronoi (também chamada de região Voronoi ou célula Dirichlet) Rk consistindo em todos os pontos que possuem distância para pk 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[editar | editar código-fonte]

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 (Pk)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, Rk, associada ao sítio Pk é o conjunto de todos os pontos em X os quais a distância para Pk não é maior do que a distância para os outros sítios Pj , 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 Rk={x in X: d(x,Pk) ≤ d(x,Pj) for all j≠k}. O Diagrama de Voronoi é simplesmente a tupla de células (Rk)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[editar | editar código-fonte]

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 Rk de Voronoi de uma determinada loja de Pk 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((a1,a2),(b1,b2))=((a1-b1)2+(a2-b2)2)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 l1, ou seja, d((a1,a2),(b1,b2))=|a1-b1|+|a2-b2|.

Propriedades[editar | editar código-fonte]

  • 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.[3] 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.[4] 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[editar | editar código-fonte]

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 Sohovivia 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 = {x1, x2, ..., xn−1} pelo Diagrama de Voronoi gerado a partir do conjunto  S − X.

Diagrama de Voronoi do ponto mais distante[editar | editar código-fonte]

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 = {p1, p2, ..., pn} 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 = {h1, h2, ..., hk} 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, hi) > dist(q, pj) para cada pj∈S com hi ≠ pj, onde dist(p, q) é a distância euclidiana entre dois pontos p e q.[5][6]

Generalizações e Variações[editar | editar código-fonte]

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. 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.[7]

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[editar | editar código-fonte]

  • 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.[5]
  • 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[editar | editar código-fonte]

Algoritmos
Related subjects

Notas e Referências

  1. ↑ Franz Aurenhammer (1991). Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345-405, 1991
  2. ↑ 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
  3. ↑ Daniel Reem, An algorithm for computing Voronoi diagrams of general generators in general normed spaces, In Proceedings of the sixth International Symposium on Voronoi Diagrams in science and engineering (ISVD 2009), 2009, pp. 144--152
  4. ↑ Daniel Reem, 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
  5. ↑ a b Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2008). Computational Geometry Third edition ed. [S.l.]: Springer-Verlag  7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.
  6. ↑ Skyum, Sven (1991). «A simple algorithm for computing the smallest enclosing circle». Information Processing Letters 37(1991)121-125  |nome2= sem |sobrenome2= em Authors list (ajuda), Contains a simple algorithm to compute the Farthest-Point Voronoi Diagram.
  7. ↑ S. Arya, T. Malamatos, and D. M. Mount, Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721–730.

Bibliografia[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

O Commons possui uma categoria com imagens e outros ficheiros sobre Diagrama de Voronoy
Obtida de "https://pt.wikipedia.org/w/index.php?title=Diagrama_de_Voronoy&oldid=63124122"