PROVA
4 OUT, SEG |
PROVA 1
|
AULA 15
6 OUT, QUA |
- Resumo da aula anterior.
- Fecho Convexo em 3-D. Antes de mostrar algoritmos para
resolver este problema, precisamos pensar em estruturas de dados para
representar poliedros em 3-D. A estrutura que usaremos é a
"winged edge".
- Estrutura de dados winged edge.
- Algoritmo Embrulho para Presente 3-D.
|
RECESSO
11 OUT, SEG |
NÃO HAVERÁ AULA.
|
AULA 16
13 OUT, QUA |
- Resumo da aula anterior.
- Algoritmo Embrulho para Presente 3-D (continuação).
- Diagramas de Voronoi: região de Voronoi; aresta de Voronoi; vértices de
Voronoi
|
AULA 17
18 OUT, SEG |
- Resumo da aula anterior.
- Algumas propriedades do Diagram de Voronoi.
- Diagrama de Delaunay.
|
AULA 18
20 OUT, QUA |
- Resumo da aula anterior.
- Algoritmo ingênuo de complexidade de tempo O(n2 log
n) para construir o Diagrama de Voronoi
- Algoritmo incremental para construir o Diagrama de Vorono.
- Algoritmo por divisão e conquista de complexidade de tempo
O(n log n) para construir o Diagrama de Voronoi.
- Algoritmo de linha de varredura de complexidade de tempo
O(n log n) para construir o Diagrama de Voronoi.
|
AULA 19
25 OUT, SEG |
- Resumo da aula anterior.
- Propriedades do Diagrama de Delaunay.
- Cota inferior para o problema de construir o Diagrama de Delaunay
(continua na próxima aula).
|
AULA 20
27 OUT, QUA |
- Resumo da aula anterior.
- Teorema 1. Qualquer algoritmo que construa uma triangularização de um dado conjunto com n pontos faz omega(n log n) operações
elementares.
- Teorema 2. Qualquer algoritmo que construa uma Diagrama de
Delaunay (Voronoi) de um dado conjunto com n sítios faz omega(n log n) operações
- Primitivas Geométricas: Left(a,b,c) é verdadeiro
se o ponto
c está à esquerda do segmento orientado ab;
Incircle(a,b,c,d) é verdeiro se o ponto d está na face esquerda da circunferência orientada pelo triângulo (a,b,c).
- Algoritmo quadrático para construir o Digrama de Delaunay.
|