14 April 2023
14:00 Doctoral defense IC room 85
Theme
Exact and Heuristic Solutions for Optimal Polygon Construction Problems
Student
Natanael Ramos
Advisor / Teacher
Cid Carvalho de Souza - Co-advisor: 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
Headlines:
| 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 |
Substitutes:
| Ricardo Dahab | IC / UNICAMP |
| Alexandre Salles da Cunha | DCC / UFMG |
| Luidi Gelabert Simonetti | COS/UFRJ |