Advanced search
Start date

Mininum convex partition problem

Grant number: 17/12523-9
Support Opportunities: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 - 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


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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list using this form.