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

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 |

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 |

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) | |