Algoritmos
2021 – trabalhos

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.

Wikipedia, Point in polygon
Hormann–Agathos (2001), The point in polygon problem for arbitrary polygons
Randolph Franklin (2018), PNPOLY - Point Inclusion in Polygon Test

26/8: triangulação de polígonos

existência, consequências, galerias de arte.

Devadoss–O'Rourke (2011), Chapter 1
O'Rourke (1987), Art Gallery Theorems and Algorithms
Narkhede–Manocha (1995), Fast polygon triangulation based on Seidel's algorithm
Kooshesh–Moret (1992), Three-coloring the vertices of a triangulated simple polygon

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