The problem of partitioning a set of weighted points in a grid of quadrilaterals

• Grant number: 15/17948-2
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Effective date (Start): January 01, 2016
• Effective date (End): April 30, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cid Carvalho de Souza
• Grantee: Mateus Augusto Bellomo Agrello Ruivo
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

This project will investigate the problem of partitioning a set of weighted points in a grid of quadrilaterals so that a given objective function is minimized. The problem is directly connected to the histogram equalization of images with more than one color scale. This technique is used in image processing to better distribute the colors in an image in order to enhance its contrast. There is no efficient algorithm to solve this problem and, possibly, none is going to be found as one decision version of the problem was shown to be NP-hard. Therefore, the goal of this project is the development of a GRASP metaheuristic to solve a variant of the problem of partitioning a set of weighted points in a grid of quadrilaterals. Due to its relevance in the image processing application cited above, the function chosen to be minimized is the maximum deviation from the mean of the sum of the weights of the points in each quadrilateral of the grid.