Proximidade: Algoritmos Fundamentais

Neste post estaremos apresentando uma grande classe de problemas que envolvem a proximidade de pontos no plano e nosso objetivo será o de lidar com todas essas tarefas aparentemente não relacionados através de um único algoritmo, que descobre, processos e armazena de forma compacta toda informação de proximidade relevante. Para fazer isso, utilizaremos um objeto matemático clássico, o diagrama de Voronoi, e vamos transformá-lo em uma estrutura computacional eficiente que permite grande melhoria sobre os melhores algoritmos previamente conhecidos. Este post foi desenvolvido a partir do conteúdo do capítulo 5, Proximidade: Algoritmos Fundamentais do livro Computational Geometry an Introduction, dos autores Franco Preparata e Michael Ian Shamos

Problema 1: (Par mais próximo): Dados N pontos no plano, encontre dois que estejam mais próximos.

Este problema é tão facilmente declarado e importante que devemos considerá-lo como uma das questões fundamentais de geometria computacional, tanto do ponto de vista de aplicações quanto de puro interesse teórico. Por exemplo, uma aplicação em tempo real é fornecida pelo problema de controle de tráfego aéreo: com alguma simplificação, os dois aviões que estão em maior perigo de colisão são os dois mais próximos.

A questão algorítmica central é se é necessário examinar cada par de pontos para encontrar a distância mínima assim determinada. Isto pode ser feito em tempo O (dN²) em  d dimensões, para qualquer d. Em uma dimensão de um algoritmo mais rápido é possível, com base no fato de todos os pares de pontos mais próximos devem ser consecutivos na ordem de classificação. Podemos, assim, classificar os dados N números reais em O (N logN) etapas e executar uma varredura linear de tempo da seqüência ordenada (x₁,x₂,...,x_n) computando x_{i +1} = 1, ..., N - 1. Este algoritmo,como será mostrado adiante, é executado em tempo ótimo.

Problema 2: (Todos vizinhos mais próximos). Dados N pontos no plano, encontre o vizinho mais próximo de cada ponto. 

O "vizinho mais próximo" é uma relação em um conjunto S de pontos como a seguinte: o ponto b é o vizinho mais próximo do ponto a, representado como b -> a , se dist(a,b) = min dist(a,c), onde c pertence a S - a.

Note que não é necessariamente verdade que se a -> b então b -> a e que um ponto qualquer não tem necessariamente apenas um único vizinho mais próximo. A solução do problema 2 é um conjunto de pares ordenados (a,b) onde a -> b.

Problema 3: (Árvore de Abrangência Euclidiana Mínima). dado N pontos no plano, construir uma árvore de comprimento total mínimo cujos vértices são os pontos dados.

Para solucionar este problemas devemos construir uma lista de N -1 pares de pontos que compreende as arestas da árvore. Tal árvore é mostrada na Figura 5.2. Este problema é um componente comum de aplicações que envolvam redes. Se alguém deseja criar um sistema de comunicação entre os nós N requerem cabos de interconexão, usando a Árvore de Abrangência Euclidiana Mínima irá resultar numa rede de custo mínimo.

Problema 4: (Triangulação). Dado N pontos no plano, juntá-los por segmentos de linha que não se intersectam, de modo que cada região interna ao fecho convexo seja um triângulo.

Sendo um grafo planar, uma triangulação em N vértices tem no máximo 3N - 6 arestas. Uma solução para o problema deve conter pelo menos uma lista dessas bordas.

Uma triangulação é mostrada na Figura 5.4. Este problema coloca-se no método de elementos finitos [Strang-Fix (1973), Cavendish (1974)] e em interpolação numérica de dados bivariados, quando os valores da função estão disponíveis em N pontos de dados irregularmente espaçados (xi,yi) e uma  aproximação da função para um novo ponto (x, y) for desejada. Um método de fazer isto é por interpolação linear por partes, na qual a superfície é função representada por uma rede de faces triangulares planas.

Problema 5: (Busca de Vizinho Mais Próximo). Dados N pontos no plano, com preprocessamento permitido, com quanta rapidez pode ser encontrado um vizinho mais próximo de um dado ponto p?

Podemos resolver este problema em tempo O(dN) em d dimensões, mas estamos interessados em usar preprocessamento para aumentar a velocidade da busca. Há uma variedade de aplicações para o qual busca rápida é mais importante do que o problema de classificação.

Um método de classificação é a regra do vizinho mais próximo [Duda-Hart (1973)], no qual estados de quando um objeto deve ser classificado variam com o número de objetos conhecidos da população. Uma aplicação semelhante ocorre na recuperação de informações, onde o registro que melhor atende a consulta é recuperado [Burkhard-Keller (1973)]; [Fricdman-Bentley-Finkel (1977)]. Se muitos objetos devem ser processados seja em tarefas de classificação [Duda-Hart (1973)] (reconhecimento de voz, identificação de partículas elementares, etc.) ou em tarefas de recuperação (melhor resposta recuperada), devemos estar preparados para realizar busca de vizinhos mais próximos com rapidez.

Problema 6: (Busca de K-Vizinhos Mais Próximos). Dado N pontos no plano, com o pré-processamento permitido, com que rapidez podemos encontrar os k pontos mais próximos para um novo ponto dado q?

Os  k-vizinhos mais próximos têm sido usados ​​para interpolação e contorno [Davis (1975)] e para a classificação (a regra k-vizinho mais próximo é mais robusta do que apenas olhar para um único vizinho).

A Abordagem de Local para Problemas de Proximidade: O Diagrama de Voronoi

Apesar da abordagem de dividir e conquistar utilizada para o problema do par de pontos mais próximo é bastante encorajadora, ela ainda não consegue resolver todos os problemas de  vizinhos mais próximos, que parecem ser apenas uma simples extensão. Na verdade, se tentarmos criar a recursão análoga para todos os vizinhos mais próximos, vemos que a forma natural de dividir o problema não induz dispersão, e não há nenhuma forma aparente de realizar a etapa de fusão em menor tempo do que tempo quadrático.Por outro lado, uma heurística valiosa para a concepção de algoritmos geométricos é olhar para a definição de "local" e tentar organizá-los em uma estrutura de dados. Numa formulação bidimensional, queremos resolver,

Problema 8 (Local de Proximidade). Dado um conjunto S de N pontos no plano, para cada ponto p em S qual é o local de pontos (x,y) no plano que estão mais próximos de p do que qualquer outros pontos de S?

Note-se que, intuitivamente, a solução do problema acima é uma partição do plano em regiões (cada região, sendo o local geométrico dos pontos (x, y) mais perto de um ponto de S do que de qualquer outro ponto de S). Observamos também que, se conhecemos esta partição, procurando-a (isto é, pela localização de um ponto q em uma região da partição), podemos resolver diretamente a busca do vizinho mais próximo (Problema 5).

Vamos agora analisar a estrutura da partição do plano. Dado dois pontos, p_i e p_j o conjunto de pontos mais próximos de p_i do que p_j é apenas a metade do plano que contém p_i que é definido pela mediatriz p_ip_j. Vamos chamar este semi-plano de H (p_ip_j). O local geométrico dos pontos mais perto de p_i do que qualquer outro ponto, que denotamos por V(i), é a interseção de N - 1 semiplanos, e é uma região poligonal convexa, não tendo mais de n - 1 lados.V(i) é chamado de polígono de Voronoi associado com p_i.