next up previous
Next: About this document ...

MAC-IME-USP CARLOS EDUARDO FERREIRA


SALA 297A TEL.: 818 6140


E-MAIL cef@ime.usp.br




Geometria Computacional

Terceira Lista de Exercícios - Entrega 24 de novembro de 1999

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 $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]

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 S1 e S2 uma parti��o de S, ou seja, $S=S_1 \cup S_2$ e $S_1 \cap S_2 = \emptyset$. Prove que se uv � um segmento de menor comprimento entre os segmentos que t�m uma ponta em cada conjunto (ou seja, $\{s_1s_2 \vert s_1 \in S_1 \mbox{ e } s_2 \in S_2\}$), ent�o uv � uma aresta da triangulariza��o de Delaunay.



next up previous
Next: About this document ...
Carlos Eduardo Ferreira
1999-10-20