sexta-feira, 31 de outubro de 2008

Diagramas de Voronoi


Abaixo você vê (vocês vêem?) uma instalação que dinamicamente simula um diagrama de Voronoi usando pessoas como pontos em um espaço delimitado. Este diagrama tem a propriedade de que, dado um conjunto de pontos, o espaço criado para cada um deles está mais próximo deste do que quaisquer dos outros.



Estes diagramas têm muitas muitas aplicações na ciência, e conheço algumas. Na ecologia, se considerarmos os pontos como tocas de predadores, seu espaço seria seu território - se um predador A entrar no espaço do predador B, este estará menos cansado do que o outro, pois terá andado menos, e B possivelmente vencerá A em um enfrentamento. Com, isso um equilíbrio se forma.

Pelo mesmo motivo, um diagrama de Voronoi pode lhe dizer como otimizar seu acesso a serviços, como qual o posto dos correios, de saúde, cartório mais próximo da sua casa ou trabalho. Ainda melhor, permite definir estratégias para alocar um novo posto de serviços, levando em conta a população que ele deve atender.


Clique na imagem para ir ao artigo, que descreve também um diagrama de Voronoi ponderado pelo número de atendimentos de cada hospital

Por fim, em computação, estes diagramas têm uma relação dual (isto é, de um para um, ou bijetiva) com uma malha triangular de Delaunay, que possui qualidades interessantes na discretização (ou seja, uma partição) do espaço. Explicar essas qualidades está um pouco fora do tema do blog (e da minha capacidade :) ), mas essa discretização permite bons resultados em cálculos numéricos onde é necessário considerar elemento por elemento de um espaço.


Em linhas sólidas, a triangulação de Delaunay, e em linhas tracejadas, o diagrama de Voronoi equivalente. Note que o conjunto de pontos de Voronoi corresponde aos vértices dos triângulos da malha

Por fim, uma coisa que eu nunca consigo deixar de pensar quando vejo diagramas de Voronoi: é cada um no seu quadrado!



Um comentário:

Carlos Hotta disse...

Ótima idéia de blog! Ficarei de olho.