Advanced search
Start date
Betweenand

Mininum convex partition problem

Grant number: 17/12523-9
Support type:Scholarships in Brazil - Master
Effective date (Start): October 01, 2017
Effective date (End): November 30, 2018
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Cid Carvalho de Souza
Grantee:Allan Sapucaia Barboza
Home 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.