Geometria computacional

Ementa do curso

  1. Introdução

    Tangentes entre um ponto e um polígono

    Algoritmo de Melkman

    Tangentes entre dois polígonos

  2. Fecho convexo no plano

    Algoritmo de Chand e Kapur

    Algoritmo de Graham

    Algoritmo de Andrew

    Algoritmo de Preparata e Hong

    Algoritmo Quickhull

    Algoritmo incremental

    Limites inferiores de complexidade

    Algoritmo de Chan

  3. Fecho convexo em dimensões superiores

    Problema V-rep x H-rep

    Dimensão, cardinalidade

    Simplexos

    Interpretação geométrica do determinante e da orientação

  4. Paradigma EGC (Exact Geometric Computation)

    Erros na aritmética de virgula flutuante

    Aritmética de precisão multipla

    Aritmética intervalar

    Aritmética filtrada

Material

Algoritmos para calcular tangentes a polígonos

Artigo de Overmars e van Leeuwen (ver teorema 3.2)

Artigo de Kirkpatrick e Snoeyink sobre tangentes a polígonos sem linha de separação

Artigo de Kirkpatrick e Snoeyink sobre prune-and-search

Artigo da Wikipedia sobre fecho convexo, e algoritmos para calcular

Resumo sobre fecho convexo

Applet demonstrativo do algoritmo de Andrew para fecho convexo

Artigo de Kettner et al. sobre exemplos de problemas de robusteza

Slides sobre arranjos de reta

Livro-texto

Computational Geometry: Algorithms and Applications

Implementação

Biblioteca CGAL

Links

Geometria computacional

Definição de Wikipedia