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
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 S1 e S2 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.
Next: About this document ...
Carlos Eduardo Ferreira
1999-10-20