|
1 |
5/Out/07 |
Feriado Nacional |
|
2 |
12/Out/07 |
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 eficientes. Tipos de
problemas geométricos. Aplicações da GC.
Configurações degeneradas em GC. Problemas
clássicos da GC.
Slides:
Introdução à GC
|
|
3 |
19/Out/07 |
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. 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 métodos
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 |
26/Out/07 |
Alguns problemas elementares da GC
(cont...).Problema Nº 2: Área de
Polígonos (cont...). Teorema da
área de polígonos. 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.
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.
Slides:
Problemas elementares da GC;
Problema do par mais próximo;
Partição de Polígonos
|
|
5 |
02/Nov/07 |
Partição de Polígonos (cont...). 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,
Invólucros Convexos (I)
|
|
6 |
09/Nov/07 |
Secção de Apresentação de Artigos
Científicos: Filipa,
Helder,
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 |
16/Nov/07 |
Secção de Apresentação de Artigos
Científicos:
Cristina & Ana Sofia,
Ana Pinto. Sandra, Marco & Rita
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.
Slides:
Invólucros Convexos (II)
|
|
8 |
23/Nov/07 |
1º Miniteste
O problema da geração de polígonos aleatórios.
Conceitos
introdutórios. Sobre o trabalho de Thomas Auer e
Martin Held de geração de polígonos simples.
Algoritmos para a geração de polígonos estrelados:
Star Universe e Quick Star. Algoritmos para a
geração de polígonos simples: Steady Growth, Space
Partitioning, Permute and Reject e 2-Opt Moves.
Variantes: Partition Growth. Sobre o trabalho de
Toussaint, Siteru e Ruso de heurísticas para a
geração de polígonos simples: Convex Botton, Two
Peasant e Radar Sweep. Geração de polígonos
ortogonais; trabalhos de O'Rourke, Tomás e Bajuelos.
Slides:
Geração de Polígonos
|
|
9 |
30/Nov/07 |
Secção de Apresentação de Artigos
Científicos:
Elena, Lara & André
Invólucros
convexo no plano (cont...)
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. Cota
inferior para o problema da determinação do
invólucro convexo. Demonstração dum applet
Java para a construções de invólucros
convexos.
Slides:
Invólucros Convexos (II)
|
|
10 |
07/Dez/07 |
Secção de Apresentação de Artigos
Científicos:
Diana & Joana
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ítmicos da determinação do número
mínimo de guardas num polígono. 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 |
|
11 |
14/Dez/07 |
Secção de Apresentação de Artigos
Científicos:
Nuno, Luís Pedro & Rui
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
|
|
12 |
21/Dez/07 |
Secção de Apresentação de Artigos
Científicos:
Cristiana
2º Miniteste |
