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