### Abstract

Suppose that two members of a finite point guard set S within a polygon P must be given different colors if their visible regions overlap, and that every point in P is visible from some point in S. The chromatic art gallery problem, introduced in [7], asks for the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of P. We study two related problems. First, given a polygon P and a guard set S of P, can the members of S be efficiently and optimally colored so that no two members of S that have overlapping visibility regions have the same color? Second, given a polygon P and a set of candidate guard locations N, is it possible to efficiently and optimally choose the guard set S ⊆ N that requires the minimum number of colors? We provide an algorithm that solves the first question in polynomial time, and demonstrate the NP-hardness of the second question. Both questions are motivated by common robot tasks such as mapping and surveillance.

Original language | English (US) |
---|---|

Title of host publication | 2011 IEEE International Conference on Robotics and Automation, ICRA 2011 |

Pages | 2302-2307 |

Number of pages | 6 |

DOIs | |

State | Published - Dec 1 2011 |

Event | 2011 IEEE International Conference on Robotics and Automation, ICRA 2011 - Shanghai, China Duration: May 9 2011 → May 13 2011 |

### Publication series

Name | Proceedings - IEEE International Conference on Robotics and Automation |
---|---|

ISSN (Print) | 1050-4729 |

### Other

Other | 2011 IEEE International Conference on Robotics and Automation, ICRA 2011 |
---|---|

Country | China |

City | Shanghai |

Period | 5/9/11 → 5/13/11 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Control and Systems Engineering
- Artificial Intelligence
- Electrical and Electronic Engineering

### Cite this

*2011 IEEE International Conference on Robotics and Automation, ICRA 2011*(pp. 2302-2307). [5979838] (Proceedings - IEEE International Conference on Robotics and Automation). https://doi.org/10.1109/ICRA.2011.5979838