Algoritmos
 2023 – 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

15/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
• Eric Haines (2001), Point in Polygon Strategies
• Randolph Franklin (2018), PNPOLY - Point Inclusion in Polygon Test

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

existência, consequências, galerias de arte; demo, dados e mais.

• Wikipedia, Polygon triangulation
• 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
• Toussaint (1993), History of Triangulation Algorithms, table

12/9: fecho convexo

algoritmos básicos, complexidade; dados e mais.

• 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 algorithm 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
• Kong–Everett–Toussaint (1990), The Graham scan triangulates simple polygons
• Skala–Smolik–Majdisova (2016), Reducing the number of points on the convex hull calculation using the polar space subdivision in E2

26/9: fecho convexo e ordenação

Implemente o algoritmo de Graham usando a função de ordenação da sua linguagem de programação. Compare pontos, não ângulos! Implemente alguns algoritmos de ordenação e meça a sua influência no desempenho do algoritmo de Graham.

• Graham (1972), An efficient algorithm for determining the convex hull of a finite planar set

3/10: triangulação

Adapte o algoritmo de Graham para triangulação de pontos. Implemente o algoritmo incremental para triangulação de pontos, a partir de uma triangulação inicial do fecho convexo. Para ambos os casos, calcule um caminho do baricentro dos pontos até a borda do fecho convexo.

• Devadoss–O'Rourke (2011), Chapter 3
• Clarkson (1996), 2dch.c

10/10: interseção de segmentos de retas

Implemente o algoritmo de varredura para detectar se há interseções em um conjunto de segmentos no plano; implemente identificação de todos os pares de segmentos que se intersectam. Teste algumas estruturas de dados para representar o estado e a fila de eventos. Teste vários conjuntos de dados: com segmentos curtos, com segmentos longos, com segmentos médios, com segmentos curtos, médios e longos.

• Cormen et al. (2009), Chapters 33, 12,13
• Sedgewick–Wayne (2011), Chapter 3
• Wikipedia, Bentley–Ottmann algorithm
• Wikipedia, Multiple line segment intersection

31/10: Grafos não-dirigidos

Leia a descrição aqui.