Exact and heuristic algorithms for solving difficult problems related to computati...

Mathematical models and algorithmic study for rectangle escape problems

Heuristics for entire programming with feasible and infeasible search paths

Send your message by email

Advanced search

Grant number: | 18/14883-5 |

Support type: | Scholarships in Brazil - Doctorate (Direct) |

Effective date (Start): | December 01, 2018 |

Effective date (End): | August 31, 2021 |

Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |

Principal Investigator: | Pedro Jussieu de Rezende |

Grantee: | Allan Sapucaia Barboza |

Home Institution: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil |

In this project, we study integer linear programing formulations and heuristics for geometric decomposition problems. In this context, geometric decomposition problems have the goal of covering, packing or partitioning a given region in the plane with objects of predetermined shapes in order to optimize a given objective function. One of the most studied geometric decomposition problems is the triangulation problem where, given a point set $P$, we want to partition the region delimited by the convex hull $CH(P)$ in triangles with vertices in $P$ and having no points of $P$ in their interior. We will study four problems: minimum convex partition problem, convex quadrangulation of bichromatic point sets problem, convex polygon class cover problem, and coarseness problem. In the minimum convex partition problem, given a point set $P$ we want to partition the region delimited by the convex hull $CH(P)$ in the minimum number of convex polygons with vertices in $P$ and having no points of $P$ in their interior. In the convex quadrangulation of bichromatic point sets problem, given two disjoint sets of points $R$ and $B$, we want to decide if it is possible to partition the convex hull $CH(R \Cup B)$ in convex quadrilaterals with vertices in $R \Cup B$ and without points of $R \Cup B$ in their interior such that each edge connects points of different sets. In the convex polygon class cover problem, given two disjoint point sets $R$ and $B$, we want to cover the points of $R$ using convex polygons without points of $B$ in their interior. Finally, in the coarseness problem, we want to determine how mixed two disjoint point sets $R$ and $B$ by partitioning the points in $R\Cup B$ using convex polygons maximizing the absolute different between the number of points of each color in the polygon with minimum absolute difference. (AU) | |