Problemas geométricos de decomposição

Resumo

Neste trabalho, estudaremos formulações de programação linear inteira e heurísticas para problemas geométricos de decomposição. Neste contexto, problemas geométricos de decomposição têm como objetivo cobrir, empacotar ou particionar uma dada região do plano com objetos de forma predeterminada de modo a otimizar uma dada função objetivo. Um dos problemas geométricos de decomposição mais estudados é o problema da triangulação, onde dado um conjunto de pontos $P$, deseja-se particionar a região delimitada pela envoltória convexa $CH(P)$ em triângulos com vértices em $P$ e sem pontos de $P$ no seu interior. Estudaremos quatro problemas: problema partição convexa mínima, problema quadrangulação convexa de conjuntos de pontos bicromáticos, problema da cobertura de classe por polígonos convexos, e problema da coesão. No problema da partição convexa mínima é dado um conjunto de pontos $P$ e deseja-se particionar a região delimitada pela envoltória convexa $CH(P)$ no menor número de polígonos convexos com vértices em $P$, sem pontos de $P$ no seu interior. No problema da quadrangulação convexa de conjuntos de pontos bicromáticos, dado dois conjuntos disjuntos de pontos $R$ e $B$, deseja-se saber se é possível particionar a envoltória convexa $CH(R \Cup B)$ em quadriláteros convexos com extremidades em $R \Cup B$ tal que cada aresta conecta pontos de conjuntos diferentes. No problema de cobertura de classe por polígonos convexos, dados dois conjuntos disjuntos de pontos $R$ e $B$, deseja-se cobrir todos os pontos de $R$ utilizando o menor número de polígonos convexos que não contenham pontos de $B$. Por fim, no problema da coesão, desejamos determinar quão misturados estão dois conjuntos disjuntos de pontos $R$ e $B$ particionando os pontos de $R\Cup $B$ em polígonos convexos de modo a maximizar a diferença absoluta entre o número de pontos de cada cor do polígono com a menor diferença absoluta. (AU)