Next: About this document ...
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
| |
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 pi do pol�gono e determina o v�rtice mais distante de pi 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 
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.
Next: About this document ...
Carlos Eduardo Ferreira
1999-10-06