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.

Exemplo de cálculo da triangulação de Delaunay diretamente, usando a abordagem incremental randomizada.

Inicialmente iremos criar um triângulo largo que deverá conter o conjunto de pontos P. Iremos adicionar pontos extras p-1 e p-2 que, juntos com o ponto de mais alta coordenada y P0 de P, formarão o triângulo que irá conter todos os demais pontos.

Isto significa que nós iremos agora computar a triangulação Delaunay de P∪{p−1, p−2} ao invés da triangulação de Delaunay de P. Depois descartaremos p-1 e p-2 juntamente com todas as arestas incidentes para obter a triangulação Delaunay de P.

Para este trabalho, temos que escolher p-1 e p-2 o mais distantes possível, para que não destruam nenhum triângulo de Delaunay de P. Devemos garantir também que eles não caiam em nenhum círculo definido por três pontos em P.

O algoritmo é randomizado incremental, de modo que adiciona os pontos em ordem aleatória e mantém uma triangulação de Delaunay do conjunto de pontos atual. Considere a adição de um ponto pr.
Primeiro, encontre o triângulo da triangulação atual que contém pr e adicione arestas de pr para os vértices deste triângulo.
Se acontecer de pr cair em uma aresta e da triangulação, temos que adicionar arestas de pr para os vértices opostos nos triângulos que compartilham e. A figura a seguir ilustra estes dois casos.

Agora temos uma triangulação, mas não necessariamente uma triangulação Delaunay. Isto porque a adição de pr pode ter tornado ilegais algumas das arestas existentes. Para resolver este problema, chamamos o procedimento LegalizeEDGE para cada aresta potencialmente ilegal. Este programa transforma arestas ilegais em arestas legais pela rotação de arestas.

Algoritmo de Triangulação Delaunay para um conjunto de pontos P de n+1 pontos

Em seguida, discutiremos os detalhes de transformar a triangulação chegarmos após a linha 9 (ou
linha 14) em uma triangulação Delaunay.

Sabemos do Teorema 9.8 que a triangulação é uma triangulação de Delaunay, se todas as suas bordas são legais. No espírito do algoritmo LEGALTRIANGULATION, nós, portanto, iremos trocar as bordas ilegais até a triangulação ser legal novamente.

A questão que permanece é que as extremidades podem tornar-se ilegais, devido à inserção de pr. Observe-se que uma aresta do pi pj que era legal antes só se torna ilegal se um dos triângulos incidentes for alterado.

Assim, apenas as arestas dos novos triângulos precisam ser verificadas. Isto é feito usando a rotina LegalizeEDGE, que testa e possivelmente rotaciona uma borda.

Se LegalizeEDGE vira uma aresta, outras arestas podem se tornar ilegal. Portanto LegalizeEDGE chama a si mesmo de forma recursiva para todas as potenciais arestas ilegais.

Computando Triangulação Delaunay usando Fecho Convexo

Há uma conexão entre o fecho convexo e a triangulação Delaunay, que foi descoberta em 1979 por Kevin Brown e completamente desenvolvida por Herbert Edelsbrunner e Raimund Seidel no início dos anos 80. O centro desta conexão envolve o paraboloide

 Seja S um conjunto de pontos no plano xy, sem 4 pontos co-circulares. Associado a cada site (x,y) um valor de "altura de terreno" de x2 + y2 . Este local estará exatamente dentro de um paraboloide. Agora encontre o fecho convexo deste conjunto de pontos em R3. Descarte as "faces de cima" deste fecho, aquelas faces que são visíveis olhando diretamente para baixo do eixo z do alto. Estas faces são chamadas de fecho convexo superior, enquanto as faces restantes são chamadas de fecho convexo inferior. O impressionante resultado da conexão entre o fecho convexo e a triangulação Delaunay é dado pelo seguinte teorema:

Dado um conjunto de pontos S em um plano xy, a triangulação Delaunay Del(S) é exatamente a projeção para o eixo xy do fecho convexo inferior dos pontos (x,  y, x2+y2).

A figura a seguir mostra 10 pontos no plano cuja triangulação resulta da projeção do fecho convexo inferior destes pontos localizados no paraboloide. A marca do círculo no plano mostra a origem em R2, o ponto no qual o paraboloide toca o plano.

Do cálculo multivariado, a equação da tangente plana ao ponto (a,b) é dada por:

Se este plano for deslocado para cima (na direção de z) pela distância de r2, obtemos um novo plano p dado por

Da geometria cônica, este plano p intercepta a paraboloide ao longo de uma elipse. A projeção dessa elipse sobre o plano xy obtida resolvendo as equações (4.1) e (4.3) produz

Prova: Escolha uma face t do fecho convexo inferior, e deixe π ser o plano definido pelos três pontos de T no parabolóide. Nós podemos mudar esse plano para baixo (na direção z) até que seja tangente à

parabolóide. Sejam (a, b​​, a2 + b2) o ponto de tangência e deixe r2 ser a quantidade de deslocamento para baixo em π. A equação do plano π é então dada por (4.3). 

Pela discussão anterior, a projeção no plano xy dos três pontos que definem t encontra-se em um círculo de raio r dada pela equação (4.4). Desde que t é uma face inferior do fecho convexo, todos os outros sites na paraboloide encontram acima de π, o que implica que se projetam para fora deste círculo de raio r. Portanto, este círculo determinado por t está vazio. pelo Teorema 3.53, a projeção de t para o plano xy é um triângulo Delaunay. Uma vez que isto é verdade para todos as faces do fecho convexo inferior, a projeção plena produz a triangulação de Delaunay.

Geometria Voronoi

Definição: A região Voronoi Vor(p) de um site p em S é

onde ||p-q|| representa a distância Euclidiana entre os pontos p e q no plano.

Vor(p) representa o conjunto de todos os pontos x que estão mais próximos de p do que qualquer outro site q em S. Os pontos que se encontram na fronteira entre as regiões não tem um único site mais próximo. O diagrama de Voronoi é a coleção destas fronteiras: o conjunto de todos os pontos no plano que tem mais de um site vizinho mais próximo.

Se existe apenas dois sites p e q em S, o diagrama de Voronoi será simplesmente o segmento de reta bissetor perpendicular ao segmento pq. Este bisetor corta o plano em 2 regiões onde a região Voronoi de p é a metade do plano que contem p:

Se S tem numerosos sites, então é necessário comparar as distâncias dos pontos entre p e os outros sites de S. Isto produz os seguintes resultados:

Teorema 4.1 - A região Voronoi Vor(p) é a intersecção de todos os semiplanos H(p,q), onde q é algum outro site de S.

Um dos resultados fundamentais da Geometria Discreta é que

Teorema 4.2 - A intersecção de qualquer (não necessariamente finito) conjunto de objetos convexos é convexo.

Como todos os semi-planos são regiões convexas, o seguinte corolário é imediato

Corolário: Todas as regiões de Voronoi são convexas.

Vamos supor que existam apenas 3 sites p, q e r no conjunto de pontos S. O diagrama de Voronoi é formado por 3 bissetores perpendiculares dos segmentos pq, pr e qr. É possível que estes bissetores não necessáriamente se cruzem em um ponto, como na figura 1(a)? A resposta é NÃO, pois de acordo com um teorema de Euclides (Elementos, Livro IV, Proposição 5). Euclides provou que os bissetores perpendiculares dos lados de um triângulo  - pqr no nosso caso, mostrado em 1(b) - devem todos passar por um único ponto.De fato este ponto é um Vértice Voronoi, é o centro do único círculo circunscrito pelo qual passam os vértices do triângulo, como ilustrado em 1(c).

Figura 1 - Bissetores e círculos circunscritos em 3 sites

O que acontece com 4 ou mais sites?
Considere os dois diagramas na Figura 2. O lado esquerdo mostra um caso em que quatro sites do ponto estão posicionados sobre a  mesma circunferência circunscrita, isto acontece quando o vértice Voronoi  tem
grau 4. No entanto, se um dos locais (tal como a parte superior esquerda) é movido ligeiramente, como na figura da direita, então o grau-4 de Voronoi se divide em dois vértices graus-3. Assim, a imagem da direita é, em certo sentido, "Genérica", enquanto a da esquerda é degenerada.

                                             Figura 2 - Os diagramas Voronoi para 4 pontos

Interseções de bissetores criam vértices de Voronoi. No entanto, certamente, nem todos esses cruzamentos tornam-se vértices Voronoi. Existe uma maneira fácil de descobrir quais os pontos no plano se tornarão vértices Voronoi? O teorema a seguir responde a esta afirmativa:

Teorema 4.6 - Seja S um conjunto de pontos com diagrama Voronoi Vor(S). Um ponto v é um vértice Voronoi de Vor(S) se e somente se existir um círculo centrado em v com 3 ou mais sites em sua fronteira e nenhum site em seu interior.

Teorema 4.9 - Seja S um conjunto de pontos com diagrama Voronoi Vor(S), e seja e um subconjunto conectado do bissetor entre os sites p e q de S. Então e é uma aresta de Voronoi de Vor(S) se e somente se para cada ponto x em e, o círculo centrado em x atravessando de p e q não contem nenhum outro site de S em seu interior ou na fronteira.

Teorema 4.10 - Um diagrama de Voronoi Vor(S) de um conjunto de pontos S tem linha de aresta infitita se e somente se todos os sites de S são colineares.

Corolário 4.11 - Para um conjunto de pontos S, o diagrama de Voronoi Vor(S) é desconectado se  e somente se todos os sites de S são colineares.

Teorema 4.12 - Seja S um conjunto de pontos com n > 2 sites, então Vor(S) tem pelo menos 2n - 5 vértices de Voronoi e 3n - 6 arestas de Voronoi.

Triangulação Delauynay

Consideremos um conjunto de pontos S interpretados como estando em uma "posição geral", o que significa que não existem 3 pontos colineares ou 2 pontos não compartilham a mesma coordenada x e que não existem 4 pontos cocirculares.

Seja T uma triangulação dos pontos do conjunto S e suponha que T possui n triângulos. A sequência de ângulos (a1,a2,a3,...,an) de T é a lista de todos os ângulos de T ordenados do menor para o maior.

Usando a sequência de ângulos podemos comparar duas diferentes triangulações de S. Como o número de triângulos de qualquer triangulação de S é uma constante, todas as triangulações possuem sequência de ângulos do mesmo comprimento.

Então (20º, 30º, 45º, 65º, 70º, 130º) é melhor do que (20º, 30º, 45º, 60º, 75º, 130º) porque 65º > 60º na primeira posição em que as sequências diferem.

A melhor triangulação é o que procuramos, mas como é que vamos encontrá-la? Acontece que existe uma maneira elegante de obter a melhor triangulação via inversão de arestas. Começamos com uma definição.

Definição: Seja e uma aresta de uma triangulação T1, e seja Q um quadrilátero em T1 formado pelos 2 triângulos que têm e como aresta comum. Se Q e convexo, deixe T2 ser a triangulação depois de inverter a aresta e em T1. Dizemos que e é uma aresta legal se T1 for maior ou igual a T2, caso contrário e é uma aresta ilegal.

Para obter a melhor triangulação do conjunto de pontos S devemos evitar o surgimento de arestas ilegais nas triangulações.

Definição: Para um conjunto de pontos S, uma triangulação Delaunay de S (Del(S)) é uma triangulação onde ocorrem apenas arestas legais.

Algoritmo de Inversão de Arestas: Seja S um conjunto de pontos em "posição geral", sem 4 pontos cocirculares. Inicie com uma triangulação T. Se T tem uma aresta ilegal, inverta a aresta e obtenha uma aresta legal. Continue invertendo arestas ilegais, movendo-se pelas arestas do grafo de S em qualquer ordem até não restarem mais arestas ilegais.

No algoritmo de Delaunay proposto, para realizar o cálculo da aresta legal será necessário a inversão de uma diagonal, o quê envolverá a comparação de 12 ângulos em duas sequências de 6 ângulos. Há uma maneira mais simples de fazer este teste usando círculos baseado em uma extensão da um teorema clássico da geometria planar:

Teorema 3.49(Thales) Para três pontos P, Q e B em um círculo, e A dentro e C fora do círculo, o ângulo PAQ é maior que  PBQ que é maior que PCQ.

Esboço da Prova: Seja O o centro do círculo. Os 3 segmentos OP, OQ e OB são radianos e tem igual comprimento. Então os triângulos POB e QOB são isóceles. Sendo assim, não é difícil mostrar que independente da posição de B no arco do círculo, o ângulo POQ é duas vezes maior que PBQ. De fato, este é o teorema de Euclides (Elementos, Livro III, Proposição 20): um ângulo inscrito em um círculo tem metade do ângulo central subtendido o mesmo arco. Isto pode ser utilizado para declarar que o ângulo PAQ é maior que PBQ e que PCQ é menor que PBQ.