Geometria Computacional é uma área de pesquisa de grande interesse em Ciência da Computação, encontrando aplicações em diversas outras áreas como, por exemplo, computação gráfica e processamento de imagens.
Conteúdo:
1. Triangularização de polígonos: teoria, primitivas geométricas, algoritmos, questões de implementação.
2. Particionamento de polígonos: particionamento em polígonos monótonos, trapezoidalização de polígonos, particionamento em polígonos convexos.
3. Fecho convexo no plano: algoritmo embrulho-para-presente, algoritmo Quickhull, algoritmo de Graham, algoritmo incremental, algoritmo de divisão-e-conquista, cota inferior.
4. Fecho convexo tridimensional: poliedros, politopos regulares, fórmula de Euler, estruturas de dados, primitivas geométricas, algoritmo embrulho-para-presente.
5. Diagrama de Voronoi: propriedades, diagrama de Delaunay, cota inferior, primitivas geométricas, algoritmo quadrático, algoritmo de divisão-e-conquista.
6. Problemas de localização e intersecção: localização de pontos em polígonos, intersecção de polígonos convexos, intersecção de semiplanos, núcleo de um polígono.
7. Problemas de proximidade: problema do par-mais-próximo, árvore geradora mínima.
8. Arranjos de retas no plano.
- Professor: Cristina Gomes Fernandes