Instituto de Matémática Pura e Aplicada



Baixar 6.07 Kb.
Encontro24.09.2019
Tamanho6.07 Kb.

Instituto de Matemática Pura e Aplicada

Geometria Computacional – 2002

2a Lista de Exercícios (para 28/05/2002)

Aluno : Sergio Coutinho de Biasi
1. Seja S um conjunto finito de pontos no 2. Sabendo que o fecho convexo de um conjunto finito de pontos no 2 é um polígono convexo cujos vértices pertecem a S, pede-se :

  • Mostre que Conv(S) é o polígono de menor perímetro que contém S.

  • Conv(S) é o polígono de menor área que contém S?

2. Seja S um conjunto finito de pontos no 2. Dê um algoritmo que decida se pS é ponto extremo de S em tempo linear.


3. Seja S um conjunto de n pontos no 2 com coordenadas inteiras entre 1 e nk.

a) Mostre como calcular o fecho convexo de S em tempo linear. DICA : Mostre como ordenar em tempo linear.

b) Por que isso não contradiz o limite inferior (nlogn)?
4. Seja S um conjunto finito de pontos no 2.

a) Mostre como decidir se p2 está em Conv(S) em tempo linear.

b) Mostre que se pConv(S) então achar o ponto de  Conv(S) mais próximo de p requer tempo (nlogn).

c) Mostre que se pConv(S) então achar o ponto de  Conv(S) mais próximo de p pode ser feito em tempo O(n).


5. Dado um polígono convexo P=p1..pn armazenado em um vetor, mostre que é possível localizar p em relação a P em tempo O(logn).
6. Mostre como completar eficientemente uma estrutura de dados representando uma triangulação (com as adjacências!) a partir de :

  • Uma lista de triângulos com “nomes” dos vértices

  • Uma lista de arestas com “nomes “ dos vértices





©aneste.org 2017
enviar mensagem

    Página principal