Diagrama de Voronoi

5:45 pm Geometria Computacional

Imagine que você deseja abrir um negócio próprio, por exemplo, uma lanchonete. Sabe-se que grande parte do sucesso do negócio é devido à escolha do ponto comercial. Suponha que você tenha um mapa com a localização de todos os seus concorrentes. Qual seria um ponto ideal para a abertura da sua lanchonete? Para ajudá-lo a responder a essa pergunta, você pode utilizar o Diagrama de Voronoi.

Um Diagrama de Voronoi, nomeado assim depois que o russo Georgy Voronoi estudou sua versão n-dimensional em 1908, pode ser definido de uma maneira simples como:
Dado um conjunto S de pontos no plano, determinar para cada ponto s em S a região V(p) em que todos os pontos p da região estão mais próximos de s do que de qualquer outro ponto s’ em S. A figura abaixo ilustra um Diagrama de Voronoi. O que o diagrama indica é que, dentro da região amarela por exemplo, qualquer ponto (no plano) está mais próximo do ponto destacado da região do que de qualquer outro ponto destacado do plano. A complexidade do algoritmo é O(n log n).

No exemplo da lanchonete, os pontos destacados seriam as lanchonetes concorrentes e o plano seria a cidade (ou bairro, região, etc.). Com isso, você poderia verificar em qual local uma lanchonete concorrente cobre uma grande área, podendo ter um potencial para a abertura de outra. Claro que a sua decisão não deve ser baseada somente no diagrama. É preciso verificar o seu público-alvo, movimentação de pessoas na região, dentre outras coisas. Além disso, se uma região não possui concorrentes, não necessariamente significa que você é um gênio de ter identificado esse ponto primeiro. Pode ser que o local realmente não seja bom para esse tipo de negócio. Bom, mas isso não vem ao caso nesse post.

Durante minha iniciação científica sobre redes de sensores sem fio, publicamos um artigo utilizando Diagramas de Voronoi para identificar áreas de cobertura redundantes. Resumindo, identificávamos nodos sensores próximos uns dos outros pela área de Voronoi e esses nodos eram considerados redundantes, pois mais de um estavam cobrindo praticamente a mesma área. Assim, um deles poderia ser desligado para economizar energia e re-ligado novamente caso por algum motivo sua área esteja descoberta.

A idéia desse post era mesmo apresentar resumidamente o Diagrama de Voronoi. Talvez possa ser aplicado em algum caso específico dos leitores.

Ps.: Não me responsabilizo por decisões de escolha de ponto comercial

1 Resposta
  1. Andre Senna :

    Date: junho 11, 2008 @ 3:17 pm

    Dei uma viajada aqui e me perguntei se nao daria pra usar esse algoritmo (que é polinomial) para resolver o problema de determinar o número cromático de grafos não-planares (NP-Completo)

    É claro que não dava mas mesmo assim fiquei curioso. :-) Cheguei a imaginar uma redução bem legal mas quando percebi havia cometido o erro clássico de reduzir o problema fácil ao difícil e não o contrário ;-P. Acho que estou ficando enferrujado…