Busca avançada
Ano de início
Entree

Problemas geométricos de decomposição

Processo: 18/14883-5
Linha de fomento:Bolsas no Brasil - Doutorado Direto
Vigência (Início): 01 de dezembro de 2018
Vigência (Término): 31 de agosto de 2021
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Cid Carvalho de Souza
Beneficiário:Allan Sapucaia Barboza
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Otimização combinatória   Geometria computacional   Programação linear inteira   Heurística

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)