Resumo:
"Este mini-curso é um convite modesto ao estudo de geometria computacional, feito através de problemas clássicos: par mais próximo, fecho convexo, interseção de segmentos e divisão de polígono. No problema do par mais próximo, são dados pontos no plano, e deseja-se determinar um par mais próximo destes pontos. Apresentamos um elegante algoritmo de divisão e conquista para este problema. Existem vários algoritmos que determinam o fecho convexo de um conjunto de pontos no plano. Apresentamos quatro deles: um algoritmo incremental, o embrulho de presente, o de Graham e o Quickhull. Estes algoritmos usam-se de técnicas bem diferentes, e mostram como um problema fundamental pode ser atacado de diversas maneiras. O bem sucedido método da linha de varredura é apresentado usando dois problemas: interseção de segmentos e divisão de polígono." |