Instituto de Matemática Pura e Aplicada

Geometria Computacional - 2001

5a Lista de Exercícios

Para 8/6/2001

1. Seja C = {p₁, p₂, ..., p_n} um conjunto de pontos de plano e D o grafo de Delaunay correspondente (armazenado em uma estrutura topológica). Suponhamos que um novo ponto p_n+1 é acrescentado a C e que o novo grafo de Delaunay passa a ser D’.

1. Mostre que todas as arestas que estão em D’, mas não estão em D, têm obrigatoriamente p_n+1 como um dos seus vértices.
2. Seja a uma aresta de D. Forneça um teste de complexidade O(1) que verifique se a continua sendo uma aresta de D’.

2. Seja C um conjunto finito de pontos do plano e sejam S e T subconjuntos disjuntos de C tais que S È T = C. Mostre que se pq é o menor segmento determinado por um ponto de S e um ponto de T, então pq é necessariamente uma aresta do diagrama de Delaunay de C.
   
3. Escreva uma rotina que, dados pontos a, b, c e d do plano, retorna verdadeiro quando d é exterior ao círculo circunscrito ao triângulo abc e falso caso contrário.
   
4. Seja S um conjunto de círculos no plano. Descreva um algoritmo de varredura que, em tempo O(n log n), determina se há dois círculos que se intersectam (considere que dois círculos não se intersectam se um está completamente contido no interior do outro).