-
Objetivos
-
- implementar e comparar experimentalmente algoritmos para cada problema
- verificar as previsões teóricas sobre desempenho
- investigar o papel de estruturas de dados, primitivas geométricas, e tarefas básicas
- reconhecer e tratar casos degenerados
-
19/8: localização de pontos em relação a polígonos
-
teorema da curva de Jordan:
Wikipedia,
prova;
dados:
countrydata e
mais.
-
26/8: triangulação de polígonos
-
existência, consequências, galerias de arte.
-
9/9: fecho convexo
-
algoritmos básicos, complexidade.
-
Devadoss–O'Rourke (2011), Chapter 2
-
O'Rourke (1988), Chapter 3
-
Notas de aula
-
Wikipedia,
Carathéodory's theorem
-
Wikipedia,
Convex hull algorithms
-
Wikipedia,
Gift wrapping algorithm
-
Jarvis (1973),
On the identification of the convex hull of a finite set of points in the plane
-
Graham (1972),
An efficient algorith for determining the convex hull of a finite planar set
-
Akl–Toussaint (1978),
A fast convex hull algorithm
-
Melkman (1987),
On-line construction of the convex hull of a simple polyline
-
Wikipedia,
Convex hull of a simple polygon