MAC 331 / MAC 5747 Geometria Computacional

O material que se encontra no formato postscript pode ser facilmente visto e impresso nas estações de trabalho do instituto e na rede sa Sala Pró-ALinux dos alunos de graduação usando o programa "ghostview". Se você esta usando um PC com MS-Windows, você pode fazer o download do GSview e o correspondente Ghostscript gratuitamente da University of Wisconsin para ver e imprimir o material abaixo.

1. Apresentação
2. Análise de algoritmos
   1. Introdução
   2. Modelo de computação
   3. Medidas de complexidade
   4. Análise assintótica
   5. Análise de algoritmos recursivos
   6. Complexidade computacional
   7. Robustez e hipótese de posição geral
   8. Exercícios
   9. Referências
3. Problema do par mais-próximo
   1. Introdução
   2. Algoritmo ingênuo
   3. Par mais-próximo na reta
   4. Par mais-próximo no plano: Um algoritmo por divisão-e-consquista
   5. Cota inferior
   6. Exercícios
   7. Referências
4. Teorema da Galeria de Arte
   1. Introdução
   2. Definições e convensões
   3. Problema da galeria de arte
   4. Teorema da galeria de arte
   5. Teoria de triangularização
   6. Exercícios
   7. Referências
5. Área de polígonos
   1. Introdução
   2. Área de um triângulo
   3. Orientação de triângulos
   4. Área de um polígono convexo
   5. Área de um quadrilátero não-convexo
   6. Teorema da área de polígonos
   7. Exercícios
   8. Referências
6. Primitivas Código em C escrito por Joseph O'Rouke.
   1. Introdução
   2. Representação de um ponto
   3. Representação de um polígono
   4. Cálculo da área de um triângulo
   5. Cálculo da área de um polígono
   6. Predicado LEFT
   7. Predicado LEFTON
   8. Predicado COLLINEAR
   9. Predicado INTERSECPROP (interseção própria)
   10. Predicado BETWEEN
   11. Predicado INTERSECT
   12. Predicado DIAGONALIE
   13. Predicado INCONE
   14. Primitiva DIAGONAL
   15. Exercícios
7. Arithmetic. Código em C, escrito por D.E. Knuth,que aparece no módulo gb_plane do Stanford Graph Base.
8. Intersecção de segmentos
   1. Introdução
   2. Cálculo do ponto de intersecção entre dois segmentos
   3. Detecção da intersecção entre dois segmentos
   4. Algoritmo para intersecção de intervalos
   5. Método da linha de varredura
   6. Algoritmo do tipo linha-de-varredura para intersecção de segmentos
   7. Cota inferior
   8. Exercícios
   9. Referências
9. Algoritmos para partição de polígonos
   1. Introdução
   2. Teste de diagonalidade
   3. Dois algoritmos ingênuos
   4. Triangularização de polígonos monótonos
   5. Partição em partes monótonas
   6. Partição em partes convexas
   7. Exercícios
   8. Referências
10. Fecho convexo planar
    1. Introdução
    2. Definições de convexidade e fecho convexo
    3. O problema
    4. Dois algoritmos ingênuos
    5. O método do embrulho para presente
    6. Algoritmo Quickhull
    7. O algoritmo de Graham
    8. Um algoritmo incremental
    9. Um algoritmo probabilístico
    10. Um algoritmo por divisão-e-consquista
    11. Cota inferior
    12. Uma aplicação: o problema do par mais-distante
    13. Exercícios
    14. Referências
11. Fecho convexo tridimensional
    1. Introdução
    2. Poliedros
    3. Politopos regulares
    4. Formula de Euler
    5. A primitiva geométrica Teste-de-Orientação
    6. O problema: Estrutura de Dados
    7. O método embrulho-para-presente
    8. Um algoritmo incremental
    9. Exercícios
    10. Referências
12. Diagramas de Voronoi e Delaunay
    1. Introdução
    2. Definições
    3. Propriedades do diagrama de Voronoi
    4. Diagrama de Delaunay
    5. Cota inferior
    6. A primitiva geométrica InCircle
    7. Um algoritmo quadrático
    8. Um algoritmo de divisão-e-conquista
    9. Aplicações
    10. Exercícios
    11. Referências
13. Problemas de intersecção
    1. Introdução
    2. Intersecção de polígonos convexos
    3. Intersecção de semiplanos
    4. Núcleo de um polígono
    5. Exercícios
    6. Referências
14. Dualidade
15. Arranjos de retas no plano
    1. Introdução
    2. Combinatória de arranjos
    3. Exercícios
    4. Referências
16. Triangularização de peso mínimo por Fábio Henrique Viduani Martinez
17. Geometria computacional de pontos em movimento por Carlos Ramon Pantaleon Dionisio