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 Ver menos

Abstract: The creation of objects from a set of points in the plane is a common task in a wide range of problems in Computational Geometry. In this thesis, we study NP-hard optimization problems where the objects being built are simple polygons having a subset of an input set of points as vertices. Applications of some of these problems arise in fields such as Pattern Recognition, Shape Reconstruction, Clustering and Geographic Information Systems. Firstly, we investigate Area-Optimal Simple Polygonization problems, where the goal is to find a simple polygon with minimum/maximum area whose vertex set coincides with a given input point set. We introduce constructive heuristics and local search procedures for them, assessing their efficacy using a public benchmark, which includes instances of up to one million points. Moreover, we also solve these problems exactly using Integer Linear Programming (ILP) formulations, including a novel one. We present new symmetry breaking and preprocessing strategies, as well as valid inequalities to improve these models. With our new formulation, we are able to outperform existing exact approaches in the literature. Lastly, we study the Geometric Knapsack Problem (GKP) where, given a set of points with associated real values and a real number c, the goal is to find a simple polygon that maximizes the sum of the values of the points enclosed by it minus its perimeter multiplied by c. We propose general preprocessing techniques for GKP, as well as, to the best of our knowledge, the first heuristic to solve it and a correction on an existing ILP model. We conduct a comprehensive experimental study to evaluate the efficacy of our methods. Furthermore, we also demonstrate an interesting theoretical result about two new local search neighborhoods that can be generalized to a wider range of problems regarding the computation of optimal simple polygons Ver menos