Notas de Aula de Geometria Computacional

Notas de aula: abaixo encontra-se o material e notas de aula que foram distribu�do ou utilizados durante as aulas. Deixarei uma c�pia de todo material desta p�gina na pasta de n�mero ?? do xerox do CAMAT.

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 (vers�o de 2000)
  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
  18. Problemas cin�ticos em Geometria Computacional por Eduardo Garcia de Freitas
  19. Problemas din�micos em Geometria Computacional por Cassio Polpo de Campos
P�gina principal de geometria computacional.
Last modified: Wed Aug 14 15:00:21 EST 2002