Advanced search
Start date
Betweenand

Geometric decomposition problems

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

Abstract

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)