MAC0331/MAC5747-1
Geometria Computacional
-Introdução
Esta página contém material variado sobre o curso acima.
Eu a preencherei conforme a evolução do curso.
Se você tiver dúvida sobre algum assunto relativo ao curso, me escreva ou passe
na minha sala!
-Provas e critérios de Avaliação
O desempenho dos alunos de graduação será avaliado por três provas, que abordarão
os trechos
do Livro do O'Rourke cobertos até a data da prova correspondente. A primeira prova
(p1) será no
dia 20/04 e será sobre os dois primeiros capítulos do O'Rourke. A segunda prova
(p2) será no dia
28/06. Haverá ainda uma prova de recuperação (pr) no dia 24/07. A média final do
curso
(mf) será dada pelo seguinte trecho em C:
mp =
(p1 + 2 * p2) / 3;
if( (mp >= 5) || (mp < 3) )
mf = mp;
else
mf = (mp +2 * pr) / 3;
A avaliação dos alunos de pós graduação será baseada em listas de exercicios e um
seminário
no final do curso.
-Bibliografia
A bibliografia do curso consiste basicamente de um livro: "Computational
Geometry in C", second edition,
de J. O'Rourke. As provas se basearão no conteúdo desse livro. Além disso, eu tratarei
alguns assuntos em
mais detalhe e apresentarei o conteúdo de alguns artigos de pesquisa. Esses artigos
estão disponíveis para
download na seção abaixo. Também exporei trechos do livro "Computational Geometry,
Algorithms and
Applications", por M. de Berg, M. van Kreveld, M. Overmans e O. Schwarzkopf. O conteúdo
dos artigos
e o livro de de Berg et. al são considerados material suplementar.
-Downloads.
Aritmética de ponto flutuante
Calculando a área de um triângulo em aritmética de ponto flutuante
Aritmética
de ponto flutuante e processamento de sinais
O algoritmo randomizado de Seidel para trapezoidalização em O(n log* n)
O algoritmo determinístico de Chazelle para trapezoidalização em O(n)
O algoritmo de Kiel e Snoeyink para decomposição de polígonos em partes convexas
O algoritmo de McCallum e Avis para cálculo de envoltória convexa de polígonos em tempo linear
O algoritmo de Melkman para cálculo de envoltória convexa de polígonos em tempo linear
Artigo de Chazelle, Liu e Magen sobre algoritmos sub-lineares
Artigo sobre o número de pontos na envoltória de conjuntos aleatórios
Notas de aula do prof. David Mount (Universidade de Maryland)
-Sobre erros e demonstrações
Exemplo de que mesmo os deuses herram (veja o comentário no fim da penúltima página)
O Teorema da curva
de Jordan
Lista de
algoritmos corretos e incorretos para calcular a envoltória convexa de polígonos em tempo linear
-Listas de exercícios
Aqui estão as listas de exercícios dos cursos de geometria
computacional em algumas universidades pelo mundo a fora. Escolha os seus exercícios
e divirta-se. Note que a ordem em que os tópicos são apresentados varia de curso
para curso, por isso não se preocupe se você não entender alguns dos exercícios
nestas listas: simplesmente ignore-os.
Em caso de dúvida nos exercícios, me procure.
Harvard 2005: prof. Gotsman
Universidade da
Califórnia em Santa Bárbara, 2005, prof. Suri.
Universidade de Massachusetts em Amhrest, 2005, Prof. Brock.
Simon
Fraser University, no Canadá, 2005 Prof. Shi.
-EPs
Primeiro EP, para 15 de junho.
Segundo EP, para 5 de julho.