14 Apr
14:00 Doctoral defense IC room 85
Exact and Heuristic Solutions for Optimal Polygon Construction Problems
Natanael Ramos
Advisor / Teacher
Supervisor: Cid Carvalho de Souza / Co-supervisor: Pedro Jussieu de Rezende
Brief summary
The construction of objects from a set of points in the plane is a common task in many problems in Computational Geometry. In this thesis, we study NP-hard optimization problems in which the objects being constructed are simple polygons that have as vertices a subset of the set of input points. Applications of some of these problems appear in areas such as Pattern Recognition, Curve Reconstruction, Clustering and Geographic Information Systems. First, we investigate Simple Optimal Area Polygonization problems that aim to find a simple minimum/maximum area polygon whose set of vertices is equal to the set of input points. We introduce new constructive heuristics and local search methods to solve these problems. We evaluate its effectiveness using a public benchmark with instances as high as a million points. Furthermore, we solve both problems exactly using Integer Linear Programming (ILP) models, including a new formulation. We present new symmetry breaking and preprocessing strategies, as well as valid inequalities to improve these models. With the proposed new formulation, we were able to surpass the results of other exact approaches existing in the literature. Finally, we study the Geometric Backpack Problem (GMP) in which, given a set of points in the plane with associated real values ​​and a real number c, the objective is to find a simple polygon that maximizes the sum of the values ​​of the points included by it minus its perimeter multiplied by c. We propose preprocessing techniques for the PMG, as well as, to the best of our knowledge, the first heuristic to solve it and a correction for an existing PLI model in the literature. We conducted an extensive experimental study to evaluate the effectiveness of the proposed methods. Furthermore, we also prove an interesting theoretical result about two new local search neighborhoods, which can be generalized to a wide range of problems related to the construction of optimal simple polygons.
Examination Board
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
Ricardo Dahab IC / UNICAMP
Alexandre Salles da Cunha DCC / UFMG
Luidi Gelabert Simonetti COS/UFRJ