O Problema de Recobrimento de Sólidos por Esferas de Diferentes Raios

Neste trabalho, apresentamos um modelo de programação matemática para o problema de recobrimento de sólidos por esferas de diferentes raios.
Dado um conjunto de esferas, possivelmente de diferentes diâmetros, e um sólido, deseja-se posicionar essas esferas de tal modo que a união delas forme uma cobertura para esse sólido, utilizando a menor quantidade possível de esferas desse conjunto. Esse problema tem aplicação no planejamento do tratamento por radiocirurgia conhecida como Gamma Knife e pode ser formulado como um problema de otimização não-convexa, com restrições quadráticas e função objetivo linear. Utilizamos técnicas de discretização a fim de trabalhar com um modelo linear. Propomos, ainda, uma heurística e uma reformulação baseada em uma estrutura de grafos, onde a clique de peso máximo é a solução ótima do modelo original, com a finalidade de encontrar boas soluções em tempos razoáveis.