Geometria Computacional

Segunda Prova - 22 de novembro de 1999

1.

(valor 2.5 pontos)
Descreva um algoritmo $O(n\log n)$ que receba dois polígonos convexos com n e m vértices ($m \le n$) e verifica se os polígonos são disjuntos. [Dá para fazer em tempo linear]

2.

(valor 2.5 pontos)
a. Considere uma pirâmide de base quadrada, e mostre como ficará a estrutura winged-edge para este poliedro.
b. Mostre o resultado de inserir uma aresta ligando dois vértices já existentes no poliedro (e, portanto, criando uma nova face).

3.

(valor 2.5 pontos)
Considere um conjunto de pontos $S=\{p_1,\dots,p_n\}$ e a triangularização de Delaunay correspondente. Mostre que, dado $p_i \in S$, a aresta que liga p_i ao seu vizinho mais próximo em S pertence à triangularização de Delaunay.

4.

(valor 2.5 pontos)
Considere o problema de dado um conjunto S com n pontos, encontrar, para cada um deles, o ponto de S mais próximo. Como você resolveria este problema se fosse dada a triangularização de Delaunay para S? Qual é a complexidade de seu algoritmo?

5.

(valor 2.0 pontos)
Escolha uma das apresentações a que você assistiu (ou leu o material a respeito) e faça um comentário a respeito, incluindo o conteúdo e a forma da apresentação.

NÃO PERCAM

Nesta semana teremos três apresentações da disciplina Geometria Computacional. Participem!!

• Quarta-feira, 24 de novembro, às 9:00 na sala 6B
  Clésio Takahashi
  Tema: ``Triangularização de peso mínimo''

• Quarta-feira, 24 de novembro, às 10:00 na sala 266A
  Eduardo Garcia de Freitas
  Tema: ``Problemas Cinéticos em Geometria Computacional''

• Quarta-feira, 24 de novembro, às 14:00 na sala 9B
  Cassio Polpo de Campos
  Tema: ``Problemas Dinâmicos em Geometria Computacional''