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



Compartilhe com seus amigos:


©aneste.org 2020
enviar mensagem

    Página principal
Universidade federal
Prefeitura municipal
santa catarina
universidade federal
terapia intensiva
Excelentíssimo senhor
minas gerais
união acórdãos
Universidade estadual
prefeitura municipal
pregão presencial
reunião ordinária
educaçÃo universidade
público federal
outras providências
ensino superior
ensino fundamental
federal rural
Palavras chave
Colégio pedro
ministério público
senhor doutor
Dispõe sobre
Serviço público
Ministério público
língua portuguesa
Relatório técnico
conselho nacional
técnico científico
Concurso público
educaçÃo física
pregão eletrônico
consentimento informado
recursos humanos
ensino médio
concurso público
Curriculum vitae
Atividade física
sujeito passivo
ciências biológicas
científico período
Sociedade brasileira
desenvolvimento rural
catarina centro
física adaptada
Conselho nacional
espírito santo
direitos humanos
Memorial descritivo
conselho municipal
campina grande