MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 818 6140

E-MAIL cef@ime.usp.br

Geometria Computacional

Segunda Lista de Exercícios - Entrega 11 de outubro de 1999

1.

Dada uma triangularização de um polígono, definimos o grafo dual G=(V,E) da triangularização da seguinte forma. O conjunto de vértices é formado pelos triângulos e há uma aresta ligando dois vértices se os triângulos correspondentes são adjacentes na triangularização. Prove ou dê um contra-exemplo: toda árvore com grau máximo 3 é o grafo dual de alguma triangularização.

2.

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?

3.

Qual a complexidade de tempo do algoritmo de triangularização ``corta-orelhas'' quando o aplicamos a um polígono que sabemos ser convexo?

4.

Construa um polígono simples que não é monótono com relação a todas as direções.

5.

O brilhante professor Edmorte sugeriu que modificássemos o algoritmo de Intersecção de Segmentos de tal forma que ao invés do algoritmo parar após detectar uma intersecção o algoritmo imprima o par de segmentos e siga no laço. Com isso, segundo o professor, o novo algoritmo estaria imprimindo a lista de todos os segmentos intersectantes, da esquerda para a direita, à medida que vão ocorrendo as intersecções. Mostre que o Professor Edmorte está duplamente enganado:
a. construa um exemplo em que a primeira intersecção encontrada não é a que se encontra mais à esquerda;
b. mostre um exemplo em que nem todas as intersecções são encontradas.