Aproximação Geométrica - 2009

Professor

Guilherme D. da Fonseca

Horário e local

Do dia 09/02/2009 ao dia 19/02/2009 às 2as, 3as e 5as, das 13:30 às 15:00 horas.

IMPA, sala 349.

Tópicos

• Introdução e Grades [2, 6, 7, 8]: Motivação, diâmetro, disco unitário contendo mais pontos, menor disco contendo k pontos.
• Quadtrees [1, 2, 3, 4]: Quadtree, quadtree compactada, índice da quadtree compactada, lemas de empacotamento, busca de região aproximada.
• Well-separated Pair Decomposition [1, 2, 5, 9]: Definição, construção e tamanho, Par mais próximo, Par mais distante, Spanner, Árvore geradora mínima.

Referências

1. Notas de aula do David Mount.
2. Notas de aproximação geométrica do Sariel Har-Peled.
3. Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Tradeoffs in approximate range searching made simpler. In SIBGRAPI 2008. IEEE, 2008.
4. Sunil Arya and David M. Mount. Approximate range searching. Comput. Geom. Theory Appl., 17(3-4):135-152, 2000.
5. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, 42(1):67-90, 1995.
6. Timothy M. Chan. Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Int. J. Comput. Geom. Appl., 12:67-85, 2002.
7. Stefan Funke, Theocharis Malamatos, and Rahul Ray. Finding planar regions in a terrain: in practice and with a guarantee. In SCG '04: Proceedings of the twentieth annual symposium on Computational geometry, pages 96-105, New York, NY, USA, 2004.
8. Sariel Har-Peled and Soham Mazumdar. Fast algorithms for computing the smallest k-enclosing disk. Algorithmica, 41(3):147-157, 2005.
9. Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, New York, NY, USA, 2007.

Slides

1. 09/02/2009: Introdução e diâmetro.
2. 10/02/2009: Disco unitário com mais pontos e menor disco com k pontos.
3. 12/02/2009: Quadtrees.
4. 16/02/2009: Lemas de empacotamento e busca de região.
5. 17/02/2009: Decomposição em pares bem separados (WSPD).
6. 19/02/2009: Spanners e árvore geradora mínima.