|
1 |
17/Set/09 |
Apresentação.
O Web site da disciplina. Generalidades sobre os objectivos da
cadeira. Metodologia de Trabalho a seguir ao
longo do semestre. Programa da disciplina.
Bibliografia . Métodos de Avaliação.
Introdução
à Geometria Computacional (GC). O que é a
Geometria Computacional (GC)?
Características gerais dos problema
geométricos. Algoritmos e eficiência
algorítmica.
Slides:
Introdução à GC
|
|
2 |
24/Set/09 |
Introdução
à Geometria Computacional (cont...). Tipos de
problemas geométricos. Aplicações da GC.
Configurações degeneradas em GC. Problemas
clássicos da GC.
Alguns problemas elementares da GC.
Preliminares. Conceitos e resultados
gerais: curva poligonal (aberta, fechada e
simples), teorema de Jordan, polígono,
orientação de um polígono, vértices convexos
vs vértices côncavos, lema de Meister,
visibilidade, polígonos convexos e
estrelados, teoremas relacionados com
polígonos convexos e estrelados.
Slides:
Problemas elementares da GC
|
|
3 |
01/Out/09 |
Alguns problemas elementares da GC.
Preliminares (cont...). Problema
Nº1: Ponto em Polígono (PinP). Diversas
aplicações deste problema. Estratégia
algorítmica para a resolução do problema
PinP. Complexidade algorítmica da solução.
Detecção e resolução dos casos degenerados.
Como acelerar o algoritmo para resolver o
problema PinP? O problema PinP para
polígonos convexos e estrelados.
Complexidade algorítmicas dos algoritmos
apresentados. Problema Nº2: Área de
Polígonos. Área de um triângulo. Como
determinar a área de um polígono convexo.
Área para polígonos arbitrários. Teorema da
área de polígonos.
Slides:
Problemas elementares da GC
|
|
4 |
08/Out/09 |
Alguns problemas elementares da GC.
Preliminares (cont...). Problema
Nº3: Centróide dum polígono. Diversas
estratégias para determinar o centróide dum
polígono. O algoritmo de O'Rourke.
Algumas aplicações. O problema do Par
mais Próximo (PmP). Enunciado e
Aplicações do problema. Algoritmo de força
bruta para o problema do PmP. O problema do
PmP em R1. Um algoritmo para o
problema do PmP do tipo "dividir-para-conquistar".
Uma estratégia "dividir-para-conquistar" do
o problema do PmP em R2. O
coração do algoritmo (fase combinar) e
observações importantes. Análise da
complexidade do algoritmo de
divisão-para-conquistar em R2.
Extensão dos resultado para Rd.
Slides:
Problemas elementares da GC;
Problema do par mais próximo
|
|
5 |
15/Out/09 |
Partição de Polígonos.
Algumas motivações. Enunciado do problema
sobre a triangulação de polígonos.
Resultados fundamentais: Existência de uma
triangulação. Não
unicidade da triangulação. Número de
triângulos de uma triangulação. Os
predicados Left e LeftOn. Algoritmo para
verificar uma diagonal. Algoritmo de força
bruta para triangular um polígono. Teorema
das duas orelhas (Meister). Algoritmo de
triangulação por corte de orelhas. Algoritmo
de triangulação de Lennes. Decomposição de
polígonos em polígonos y-monótonos. Triangulação de
polígonos monótonos. Problemas e resultados
fundamentais. Triangulação de polígonos
simples em O(n log n). Resumo de
triangulação de polígonos.
Slides:
Partição de Polígonos
|
|
6 |
22/Out/09 |
Secção de Apresentação de Artigos
Científicos:
João Pedro Ramos: Triangulações vs
Pseudotriangulações
Invólucros
convexo no plano. Definição do problema.
Apontamentos históricos. Definições
equivalentes de invólucros convexos.
Resultados preliminares. Determinação de
invólucros convexos no plano. Algoritmos
ingénuo Nº1. Pontos extremos. Algoritmo
Ingénuo Nº2. Arestas extremas. Algoritmo de
Jarvis (gift wrapping). Análise da
complexidade e exemplo do algoritmo de
Jarvis.
Slides:
Invólucros Convexos (I)
|
|
7 |
29/Out/09 |
Invólucros
convexo no plano (cont...). Algoritmo QuickHull (algoritmo de
divisão-e-conquista). Ideia base do
algoritmo. Fases do algoritmo Quickhull. Análise da complexidade do
algoritmo. Heurísticas
alternativas a aplicar na fase de pre-processamento do algoritmo QuickHull. Exemplos.
Algoritmo de Graham: o primeiro algoritmo
óptimo. Ideia geral do algoritmo de Graham.
Organigrama do algoritmo. Exemplo de
execução do algoritmo. Análise da
complexidade. Observações relevantes ao
algoritmo de Graham. Algoritmo
Incremental. Ideia geral. Organigrama do
algoritmo. Análise da complexidade do
algoritmo incremental. Exemplo de execução.
Algoritmo MergeHull. Generalidades do
algoritmo. Organigrama do algoritmo
MergeHull. Algoritmo para determinar as
tangentes (superior e inferior) aos
invólucros convexos. Análise da
complexidade do algoritmo MergeHull. Demonstração dum applet
Java para a construções de invólucros
convexos.
Slides:
Invólucros Convexos (II)
|
|
8 |
05/Nov/09 |
Secção de Apresentação de Artigos
Científicos:
Alexandra Alves
Invólucros
convexo no plano (cont...). Notações
assimptóticas
Q
e
W.
Exemplos. Cálculo do diâmetro dum conjunto
de pontos utilizando invólucros convexos.
Scan - uma variante do algoritmo de Graham.
Cota inferior para o problema do cálculo do
invólucro convexo. Redução do problema do
cálculo do invólucro convexo no plano ao
problema de ordenação de números reais. O
problema do cálculo do invólucro convexo dum
polígono simples. Preliminares e estratégias
gerias.
Slides:
Invólucros Convexos (III)
|
|
9 |
12/Nov/09 |
1º Miniteste
Problemas de cobertura com alcance
limitado (Inês Pereira de Matos):
Boa iluminação, k-cobertura, diagrama
de Voronoi Envolvente e rotas seguras.
|
|
10 |
19/Nov/09 |
Secção de Apresentação de Artigos
Científicos:
Salomé Pereira
O
problema da Galeria de Arte. O problema
original. Teorema da Galeria de Arte (Chvátal).
Exploração empírica do problema da Galeria
de Arte. A necessidade dos Floor(n/3)
guardas. Esboço da prova de Chvátal. A prova
de Fisk. Algoritmo de Avis e Toussaint
para colocar os Floor(n/3) guardas. Galerias
com salas rectangulares. Galerias com salas
no rectangulares. Relação entre o número de vértices reflexos e
o numero de guardas num polígono. O problema algorítmico da determinação do número
mínimo de guardas num polígono.
Slides:
Galeria de Arte
|
|
11 |
26/Nov/09 |
Participação nas provas de doutoramento:
Ana Mafalda Martins,
"Optimização Geométrica em Problemas de
Visibilidade: Soluções Meta-heuristicas e Exactas",
especialização em Geometria Computacional).
|
|
12 |
03/Dez/09 |
Secção de Apresentação de Artigos
Científicos:
Flávio Rino
O
problema da Galeria de Arte (cont). O problema Minimum Vertex Guard. Complexidade do
problema MVG para polígonos simples (com e
sem buracos). O algoritmo de aproximação de
Ghosh. Algumas variantes do problema da
Galeria de Arte: (i) polígonos
ortogonais; algoritmo para a colocação dos
Floor(n/4) em polígonos ortogonais; (ii)
guardas em polígonos ortogonais com buracos;
(iii) iluminação com reflectores; (iv) rotas
de vigilância; (v) guardas vigiados.
Slides:
Galeria de Arte
|
|
13 |
10/Dez/09 |
Secção de Apresentação de Artigos
Científicos:
José Rocha & João Carvalho
Problemas de
Proximidade:
Diagramas de Voronoi
(DV).
Introdução.
Histórico.
Definições e
observações gerais.
Construção de DV
para conjuntos de
geradores com três e
quatro pontos.
Propriedades dos
Diagramas de Voronoi:
(i) vértices e
arestas dos DV, (ii)
círculo (ii) círculo
vazio, (iii) círculo
circunscrito, (iv)
relação entre o DV e
o invólucro convexo
dum conjunto de
pontos, (v) número
de pontos e arestas
dum DV. Alguns
métodos para a
construção dos DV:
(a) elementar
(intersecção de
semi-planos), (b)
incremental, (c)
divisão e conquista,
(d) método de
Fortune.
Triangulação de
Delaunay: definição
e duas propriedades
básicas.
Slides:
Diagramas de Voronoi
|
|
14 |
17/Dez/09 |
2º Miniteste |
