Largest Empty Circle

Sobre o problema I, da prova de 2004 da seletiva interna para a maratona de programação da USP, chamado Centro de Convenções.

Esse problema é um caso especial do “largest empty circle”, descrito aqui. Para resolver esse problema acho que tem que ser feito o seguinte:

Primeiro vc tem que gerar o diagrama de Voronoi do seu plano. Suponha que seu plano seja formado por um conjunto de n pontos: p1, p2, …, pn. Esse diagrama é uma divisão do plano em regiões de maneira que as arestas dessas regiões são formadas por pontos equidistantes de pi e pj. Cada vértice da região é um ponto equidistante de três ou mais pontos. Portanto, em cada região só existe um ponto pi, e aquela região contém todos os pontos que são mais próximos de pi do que de qualquer outro do plano.

Um diagrama de Voronoi pode ser construído com o algoritmo de Fortune (não achei trivial, por isso não implementei esse algoritmo =/ ).

Dado que a região foi construída, a maior circunferência que não contém nenhum pi terá o centro localizado em um dos vértices desse diagrama. Logo, basta percorrer a lista de vértices e verificar qual é a distância para os três (ou mais) pontos que definiram esse vértice.

A construção do diagrama é feita em O(n log n), o que é maior que o custo linear de percorrer os vértices para encontrar o centro do círculo procurado, logo, essa é a complexidade do algoritmo.