Defesa de Doutorado de Breno Piva Ribeiro

Título do Trabalho
Encontrando Estruturas Geométricas com Número de Trespasse Mínimo
Candidato(a)
Breno Piva Ribeiro
Nível
Doutorado
Data
26/02/20162016-02-25 21:00:00 2016-02-25 21:00:00 Defesa de Doutorado de Breno Piva Ribeiro Encontrando Estruturas Geométricas com Número de Trespasse Mínimo Auditório do IC 2 - Sala 85 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00 h
Local
Auditório do IC 2 - Sala 85
Orientador(a)
Cid Carvalho de Souza (IC/UNICAMP)
Banca Examinadora

Titulares:
Cid Carvalho de Souza (IC/UNICAMP)
Alexandre Salles da Cunha (DCC/UFMG)
Cláudio Nogueira de Meneses    (CMCC/UFABC)
Fábio Luiz Usberti (IC/UNICAMP)
Pedro Jussieu de Rezende (IC/UNICAMP)
Suplentes:
Flávio Keidi Miyazawa (IC/UNICAMP)
Lehilton Lelis Chaves Pedrosa (IC/UNICAMP)
Carlos Eduardo Ferreira (IME/USP)

Resumo

Problemas de trespasse têm sido investigados há tempos em Geometria Computacional pois aplicações para eles são encontradas em uma grande variedade de áreas. Em geral, a entrada é formada por dois conjuntos de objetos geométricos: o conjunto, finito ou infinito, $\mathcal{L}$ de trespassadores e o conjunto $\mathcal{O}$. Uma solução viável é um subconjunto $\mathcal{O}'$ de $\mathcal{O}$ satisfazendo uma certa propriedade estrutural $\pi$. Dado $\mathcal{O}'$, o número de trespasse de $\ell\in\mathcal{L}$ é a quantidade de elementos de $\mathcal{O}'$ intersectados por $\ell$. O número de trespasse de $\mathcal{L}$ relativo a $\mathcal{O}'$ é o número de trespasse máximo dos seus elementos. O objetivo do problema é achar o subconjunto de $\mathcal{O}$ satisfazendo a propriedade $\pi$ com o menor número de trespasse possível. Esta tese traz contribuições tanto teóricas quanto experimentais para alguns problemas de trespasse. Em \cite{FeketeLM04,FeketeLM08}, Fekete, L\"{u}bbecke e Meijer resolveram o problema aberto a respeito da complexidade de encontrar uma árvore geradora com número de \emph{trespasse} mínimo. Eles também mostraram que achar um emparelhamento perfeito com número de \emph{trespasse} mínimo é \np-difícil. Modelos de programação inteira para os problemas foram apresentados. Porém, muito poucos experimentos computacionais foram realizados. Nesta tese estudamos modelos de programação inteira para encontrar emparelhamentos perfeitos, árvores geradoras e triangulação com número de trespasse mínimo. Com base nestas formulações, apresentamos algoritmos exatos e heurísticas Lagrangianas para resolvê-los. Estes algoritmos mostraram que as heurísticas Lagrangianas provêem soluções com boa qualidade, frequentemente ótimas, em um breve espaço de tempo. De todos os dez problemas e variantes discutidos em \cite{FeketeLM08}, para apenas três deles a complexidade não foi provada: Triangulação com Número de \emph{Trespasse} Mínimo, casos paralelo aos eixos e geral, e Triangulação com Número de \emph{Cruzamento} Mínimo, caso geral. Nesta tese provamos que estes três problemas são \np-difíceis. Outro problema de \emph{trespasse} mínimo é apresentado em \cite{AbamABK11} e também estudado em \cite{DurocherM12}. Este problema pede por uma partição retangular com número de \emph{trespasse} mínimo em um polígono retilinear. Embora a complexidade do problema ainda seja desconhecida, em \cite{AbamABK11} um algoritmo de 3-aproximação é apresentado. Em \cite{DurocherM12} um modelo de programação inteira é dado e uma 2-aproximação reivindicada. Nesta tese fortalecemos a formulação introduzida em \cite{DurocherM12}. Também propomos um modelo alternativo e comparamos os dois teórica e computacionalmente. Além disso, mostramos que o algoritmo proposto em \cite{DurocherM12} não provê uma 2-aproximação para o problema.