Próxima palestra

Yoshiko Wakabayashi, IME-USP

Empacotamento de círculos e esferas: complexidade e algoritmos

27.03.2020

Problemas sobre empacotamento de objetos como círculos e esferas têm recebido atenção de matemáticos há muitos séculos, tendo alguns deles permanecido abertos até recentemente, quando soluções bem complexas foram encontradas.

Um problema clássico dessa natureza, talvez o mais famoso, é o de encontrar um arranjo — o mais denso possível — de esferas de mesmo raio no espaço euclidiano 3-dimensional. Uma solução para este problema foi conjecturada por Kepler em 1611, mas apenas em 1998 Thomas Hales anunciou ter encontrado uma prova. Outros quase 20 anos foram necessários até que Hales e seus colaboradores conseguissem publicar uma prova formal numa revista (Forum of Mathematics, Pi, 2017). A versão 2-dimensional deste problema (caso de círculos) recebeu atenção de Lagrange (1773), Gauss (1831), e outros, até ser provada formalmente em 1940 por Fejes Tóth.

Nesta palestra, comentaremos brevemente resultados sobre alguns problemas clássicos, e focaremos aspectos algorítmicos e computacionais de problemas de empacotamento que têm sido investigados mais recentemente por pesquisadores da área de computação.

Em especial, destacaremos o problema de empacotar um conjunto finito de círculos de tamanhos variados em um menor número possível de quadrados unitários. Mencionaremos resultados sobre este problema e outros correlatos, com ênfase em algoritmos de aproximação (algoritmos eficientes com garantia de qualidade).