Mininum convex partition problem

• Grant number: 17/12523-9
• Support Opportunities: Scholarships in Brazil - Master
• Start date: October 01, 2017
• End date: November 30, 2018
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cid Carvalho de Souza
• Grantee: Allan Sapucaia Barboza
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this project, we study integer linear programming formulations and heuristics for the Minimum Convex Partition Problem. A convex partion with respect to a set $P$ of points in the plane is a planar division whose vertices are the points of $P$ and edges are a subset of the line segments with extreme points in P. The edges of the convex hull CH(P) of P define the unbounded face and all internal faces are convex polygons. In the Mininum Convex Partition Problem, we want to find a convex partition with the mininum number of faces.Our goal is to investigate these problems through a polyhedral study leading to an exact algorithm and developing heuristics, analyzing these alternatives empirically using a benchmark that should be available in the public domain. Furthermore, we intend to develop a graphical interface to visualize instances and evaluate the solutions generated by the implemented algorithms. (AU)