Material de MAC 747 Geometria Computacional

• Primitivas (postscript) A implementação de algumas primitivas em C (código escrito por Joseph O'Rourke).
• Algoritmo de Triangularização (postscript) Algumas funções em C que implementam um algoritmo para triangularização de um polígono (código escrito por Joseph O'Rourke).
• Algoritmo linear para triangularização de polígonos monótonos (postscript).
• Trapezoidalização de um polígono (postscript da transparência).
• Partição de polígonos em polígonos monótonos (postscript das nostas de aula).
• Partição de polígonos em polígonos monótonos (postscript da transparência).
• Partição de polígonos em partes convexas (postscript das notas de aula).
• Fecho convexo no plano (postscripts das notas de aula).
  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 de divisão-e-consquista
  10. Cota inferior
  11. Referências
• Fecho convexo tridimensional (postscripts das notas de aula).
  1. Introdução e Poliedros
  2. Politopos regulares
  3. Fórmula de Euler
  4. Uma primitiva geométrica
  5. O problema: Estruturas de dados
  6. O método do embrulho para presente
  7. Referências
• Diagrama de Voronoi (postscripts das notas de aula).
  1. Introdução
  2. Definições
  3. Propriedades do diagrama de Voronoi
  4. Diagrama de Delaunay
  5. Cota inferior
  6. Uma primitiva geométrica: InCircle
  7. Um algoritmo quadrático
  8. Um algoritmo de divisão-e-conquista
  9. Aplicações
  10. Referências
• Problemas de intersecção (postscripts das notas de aula).
  1. Introdução
  2. Intersecção de polígonos convexos
  3. Intersecção de semiplanos
  4. Núcleo de um polígono
  5. Referências
• Arranjos de retas no plano (postscripts das notas de aula).
  1. Introdução
  2. Combinatória de arranjos
  3. Referências