AULA 0
2 AGO, SEG |
NÃO HOUVE AULA.
|
AULA 0
4 AGO, QUA |
NÃO HOUVE AULA.
|
AULA 1
9 AGO, SEG |
- Descrição da disciplina: contéudo, bibliografia, critério de avaliação.
- Introdução: problemas geométricos na antiguidade, problemas geométricos
algorítmicos e geometria computacional moderna.
- O Problema do Par Mais
Próximo no plano: algoritmo ingênuo (1a. idéia: calcular a distância entre
cada par de pontos, algoritmos O(n2)).
- O Problema do Par Mais Próximo na reta: algoritmo de complexidade de
tempo O(n log(n)).
- O Problema do Par Mais Próximo no Plano: algoritmo por
divisão-e-conquista de complexidade de tempo O(n log(n)) (continua na
próxima aula).
Aviso. Para inscrever-se na lista de discussão da disciplina veja
Lista de discussão desta disciplina.
|
AULA 2
11 AGO, QUA |
- Revisão da aula anterior.
- Problema do Par Mais Próximo no Plano no plano (continuação): algoritmo
por divisão-e-conquista de complexidade de tempo O(n log(n));
detalhes de implementação para que o algoritmo tenha complexidade de tempo
O(n log(n)); Análise da complexidade de tempo do algoritmo
resultante;
- Problema geométricos elementares no plano: equação da reta passando por
dois pontos; colinearidade de pontos; paralelismo entre retas; orientação de
triângulos; semiplano positivo e negativo; detalhes de implementação.
- Polígonos: representação de polígonos; polígonos simples; polígonos
convexos.
|
AULA 3
16 AGO, SEG |
- Revisão da aula anterior.
- Problema A. Dado um polígono simples P (através de uma
listas dos seus vértices em ordem anti-horária) e um ponto ponto q,
determinar se q está no interior de P.
- Algoritmo de complexidade de tempo O(n) para o Problema A.
- Problema B. Dado um polígono simples convexo P
(através de uma listas dos seus vértices em ordem anti-horária) e um ponto
ponto q, determinar se q está no interior de P.
- Algoritmo por divisão e conquista de complexidade de tempo O(log n)
para o Problema B.
|
AULA 4
18 AGO, QUA |
- Revisão da aula anterior.
- Problema da Intesecção de Segmentos. Dados n segmentos,
verificar se existem dois segmentos que se interceptam.
- Algoritmo óbvio de complexidade de tempo O(n2).
- Algoritmo por linha de varredura de complexidade de tempo O(n log n).
|
AULA 5
23 AGO, SEG |
- Revisão da aula anterior.
- Implementação e análise do algoritmo por linha de varredura para o
Problema da Intersecção de Segmentos.
- Problema C. Dado um polígono convexo P através de um
lista de seus vértices em ordem anti-horária, determinar, para cada
vértice de P, um vértices mais distante dele.
- Algoritmo óbvio de complexidade de tempo O(n2).
- Análise mais cuidadosa do problema usando o fato de que o polígono
dado é convexo: se yu e vx são arestas de P =
(...y,u,...,v,x,...) então
l (yu) + l (vx) < l (yv) + l (ux), onde l (ab) denota o
comprimento do segmento com extremos a e b.
- Algoritmo linear para o Problema C (que usa a observação acima).
|
AULA 6
25 AGO, QUA |
- Revisão da aula anterior.
- Continuação da implementação e da análise do algoritmo linear para o
Problema C (Algoritmo Reduz).
- Triangularização de Polígonos (por diagonais): aplicações; diagonal
de um polígono.
- Problema da Triangularização de Polígonos.
|
AULA 7
30 AGO, SEG |
- Revisão da aula anterior.
- Dizemos que s= pi pj é diagonal de um
polígono P=(p1, p2 ,..., pn) se
- pi e pj não são adjacentes;
- s não intersecta nenhuma aresta de P que não se
adjacente a pi ou pj
- s é interior ao polígono P.
- Determinação se um segmento pi pj é
diagonal de um polígono em tempo constante.
- Teoria sobre polígonos:
- Todo polígono tem um vértice convexo.
- Todo polígono com pelo menos 4 vértices tem uma diagonal.
- Teorema. Todo polígono com pelo menso 4 vértices pode ser
particionado em triângulos através da inclusão de diagonais.
- Toda triangularização de um polígono (pelo menos 3 vértices) usa
n - 3 diagonais e divide o polígono em n-2 triângulos.
- A soma dos ângulos internos de um polígono (pelo menos 3
vértices) é (n-2) Pi.
- Algoritmo para triangularizaçào de polígonos de complexidade
O(n4) (força bruta).
- Toda diagonal da forma
pi pi+1 de um polígono é dita uma orelha
do polígono.
- Teorema. (Duas orelhas) Todo polígono com pelo menos 4 vértices
possui pelo menos duas orelhas que não têm interior comum.
|