Busca avançada
Ano de início
Entree

Problemas geométricos de decomposição

Processo: 18/14883-5
Modalidade de apoio:Bolsas no Brasil - Doutorado Direto
Vigência (Início): 01 de dezembro de 2018
Vigência (Término): 31 de agosto de 2022
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Pedro Jussieu de Rezende
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
Palavra(s)-Chave do Pesquisador:Combinatória Poliédrica | Geometria Computacional | Otimização Combinatória | programação linear inteira | Otimização Combinatória

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)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações científicas
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
SAPUCAIA, ALLAN; REZENDE, PEDRO J. DE; SOUZA, CID C. DE. Solving the minimum convex partition of point sets with integer programming. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v. 99, . (18/14883-5, 18/26434-0, 14/12236-1)
SAPUCAIA, ALLAN; DE REZENDE, PEDRO J.; DE SOUZA, CID C.; GERVASI, O; MURGANTE, B; MISRA, S; GARAU, C; BLECIC, I; TANIAR, D; APDUHAN, BO; et al. Solving the Coarseness Problem by ILP Using Column Generation. COMPUTATIONAL SCIENCE AND ITS APPLICATIONS, ICCSA 2021, PT V, v. 12953, p. 16-pg., . (14/12236-1, 18/26434-0, 18/14883-5)
Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
BARBOZA, Allan Sapucaia. Geometric decomposition problems. 2022. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.