Geometric decomposition problems

• Grant number: 18/14883-5
• Support Opportunities: Scholarships in Brazil - Doctorate (Direct)
• Start date: December 01, 2018
• End date: August 31, 2022
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Pedro Jussieu de Rezende
• Grantee: Allan Sapucaia Barboza
• Host 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)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

SAPUCAIA, ALLAN; DE REZENDE, PEDRO J.; DE SOUZA, CID C.; GERVASI, O; MURGANTE, B; MISRA, S; GARAU, C; BLECIC, I; TANIAR, D; APDUHAN, BO; et al. Solving the Coarseness Problem by ILP Using Column Generation. COMPUTATIONAL SCIENCE AND ITS APPLICATIONS, ICCSA 2021, PT V, v. 12953, p. 16-pg., 2021-01-01. (14/12236-1, 18/26434-0, 18/14883-5)

SAPUCAIA, ALLAN; REZENDE, PEDRO J. DE; SOUZA, CID C. DE. Solving the minimum convex partition of point sets with integer programming. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v. 99, DEC 2021. (18/14883-5, 18/26434-0, 14/12236-1)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

BARBOZA, Allan Sapucaia. Problemas geométricos de decomposição. 2022. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.