Geometria Computacional

Primeira Prova - 4 de outubro de 1999

NOME DO ALUNO :
ASSINATURA:

INSTRUÇÕES

1.

A prova pode ser feita a lápis.

2.

A prova consta de 4 questões. Verifique antes de começar a resolver a prova se o seu caderno de questões está completo.

DURAÇÃO DA PROVA: 2 horas

BOA SORTE!!!!

	Nota
Questão 1
Questão 2
Questão 3
Questão 4
TOTAL

1.

(valor 2.5 pontos)
a. Escreva um algoritmo MaisLonge que recebe um polígono convexo P e um vértice p_i do polígono e determina o vértice mais distante de p_i no polígono.
b. Qual a complexidade de seu algoritmo? Justifique.

2.

(valor 2.5 pontos)
Um disco consiste de uma circunferência e seu interior, e pode ser representado pelo seu centro e raio. Descreva um algoritmo $O(n \log n)$ para verificar se dados n discos, dois deles se interceptam.

3.

(valor 2.5 pontos)
a. Um polígono simples de n vértices pode ter uma única triangularização?
b. Quais polígonos simples de n vértices têm o maior número de triangularizações distintas?
c. Qual a complexidade de tempo do algoritmo de triangularização ``corta-orelhas'' quando o aplicamos a um polígono que sabemos ser convexo?

4.

(valor 2.5 pontos)
Dizemos que um polígono P é estrelado se existe um ponto em seu interior que ``enxerga'' todos os vértices de P. Na figura abaixo vemos um polígono estrelado e o fecho convexo de seus vértices.
a. Escreva um algoritmo FechodeEstrelado que recebe um polígono estrelado P e determina o fecho convexo dos vértices do polígono.
b. Qual a complexidade de seu algoritmo? Justifique.