The chromatic art gallery problem

• Grant number: 13/25104-3
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: February 01, 2014
• End date: April 30, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Pedro Jussieu de Rezende
• Grantee: Mauricio Jose de Oliveira Zambon
• Supervisor: Sándor P. Fekete
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: University of Technology Braunschweig, Germany
• Associated to the scholarship: 12/24993-6 - Exact Solutions for the Chromatic Art Gallery Problem, BP.MS

Abstract

The recently proposed Chromatic Art Gallery Problem (CAGP) has had some theoretical results presented in the literature but no studies concerning exact algorithms have been done, so far. The CAGP is related to the well known Art Gallery Problem (AGP). Contrary to the original AGP, in this variant, we are interested in minimizing the number of colors used in a valid coloring of a set of guards that covers a given gallery, represented as a polygon. Here, a coloring is valid if any two guards whose visibility polygons intersect are assigned different colors. Notwithstanding the advances we have achieved towards designing the first algorithmic solution to the CAGP with proven optimality, the proposed scientific visit to the Technische Universität Braunschweig is expected to improve the results already achieved in two fronts. Firstly, to enhance our current method for finding exact solutions to the CAGP and, secondly, to make progress towards an NP-hardness proof for the problem. As a side benefit, the collaboration between the research groups from TUB and UNICAMP will be strengthened. (AU)