MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 818 6140

E-MAIL cef@ime.usp.br

1.

No problema de determinar o fecho convexo de n pontos dados on line, os pontos são dados um a um, sem uma ordem pré-estabelecida. Deseja-se a cada ponto dado calcular o fecho convexo do conjunto até então. Descreva um algoritmo para resolver esse problema e faça uma análise da complexidade desse algoritmo.

2.

Descreva um algoritmo linear que receba dois polígonos convexos (não necessariamente disjuntos) e calcula o seu fecho convexo.

3.

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

4.

Descreva um algoritmo que receba um poliedro convexo no espaço, através de sua lista de faces, e um ponto p e verifica se esse ponto está no interior ou exterior desse poliedro.

5.

Considere um poliedro representado por uma estrutura winged-edge.
a. Escreva um algoritmo que, dada uma face F, obt�m todos os v�rtices desta face em tempo linear no n�mero de v�rtices de F.
b. Escreva um algoritmo que, dado um v�rtice v, obt�m todos os v�rtices adjacentes a v em tempo linear no n�mero de arestas incidentes a v.

6.

Considere um tetraedro representado pela estrutura winged-edge como feito em sala de aula, e mostre o resultado de inserir uma aresta ligando dois v�rtices j� existentes no poliedro (e, portanto, criando uma nova face).

7.

Descreva um algoritmo linear que dada a triangulariza��o de Delaunay para um conjunto de pontos S, constr�i o diagrama de Voronoi para este conjunto de pontos.

8.

Descreva um conjunto S de n pontos (arbitr�rio) que n�o contenha quatro pontos cocirculares tal que a triangulariza��o de Delaunay tem um v�rtice de grau n-1.

9.

Seja S um conjunto de pontos no plano e S₁ e S₂ uma parti��o de S, ou seja, e . Prove que se uv � um segmento de menor comprimento entre os segmentos que t�m uma ponta em cada conjunto (ou seja, ), ent�o uv � uma aresta da triangulariza��o de Delaunay.

• About this document ...