14 abr 2023
14:00 Defesa de Doutorado Sala 85 do IC
Tema
Exact and Heuristic Solutions for Optimal Polygon Construction Problems
Aluno
Natanael Ramos
Orientador / Docente
Cid Carvalho de Souza - Coorientador: Pedro Jussieu de Rezende
Breve resumo
A construção de objetos a partir de um conjunto de pontos no plano é uma tarefa comum
em vários problemas em Geometria Computacional. Nesta tese, estudamos problemas de
otimização NP-difíceis nos quais os objetos sendo construídos são polígonos simples que
têm como vértices um subconjunto do conjunto de pontos de entrada. Aplicações de alguns
desses problemas aparecem em áreas como Reconhecimento de Padrões, Reconstrução de
Curvas, Clustering e Sistemas de Informação Geográfica. Primeiramente, investigamos
problemas de Poligonizações Simples de Área Ótima que têm como objetivo encontrar um
polígono simples de área mínima/máxima cujo conjunto de vértices seja igual ao conjunto
de pontos de entrada. Introduzimos novas heurísticas construtivas e métodos de busca
local para resolver esses problemas. Avaliamos sua eficácia usando um benchmark público
com instâncias que chegam a ter até um milhão de pontos.
Ademais, resolvemos os
dois problemas de maneira exata usando modelos de Programação Linear Inteira (PLI),
incluindo uma nova formulação. Apresentamos novas estratégias de quebra de simetria e
preprocessamento, bem como desigualdades válidas para melhorar esses modelos. Com a
nova formulação proposta, fomos capazes de superar os resultados de outras abordagens
exatas existentes na literatura. Por fim, estudamos o Problema da Mochila Geométrica
(PMG) no qual, dado um conjunto de pontos no plano com valores reais associados e
um número real c, o objetivo é encontrar um polígono simples que maximize a soma
dos valores dos pontos inclusos por ele decrescida de seu perímetro multiplicado por c.
Nós propomos técnicas de preprocessamento para o PMG, bem como, pelo melhor do
nosso conhecimento, a primeira heurística para resolvê-lo e uma correção para um modelo
PLI existente na literatura. Conduzimos um extenso estudo experimental para avaliar
a eficácia dos métodos propostos. Além disso, também provamos um resultado teórico
interessante sobre duas novas vizinhanças de busca local, que pode ser generalizado para
uma ampla gama de problemas relacionados à construção de polígonos simples ótimos.
Banca examinadora
Titulares:
| Cid Carvalho de Souza | IC/UNICAMP |
| Cristiano Arbex Valle | DCC/UFMG |
| Anand Subramanian | CI/UFPB |
| Guilherme Pimentel Telles | IC/UNICAMP |
| Flávio Keidi Miyazawa | IC/UNICAMP |
Suplentes:
| Ricardo Dahab | IC/UNICAMP |
| Alexandre Salles da Cunha | DCC/UFMG |
| Luidi Gelabert Simonetti | COS/UFRJ |