How many landmark colors are needed to avoid confusion in a polygon?

Lawrence H. Erickson, Steven M. La Valle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publication2011 IEEE International Conference on Robotics and Automation, ICRA 2011
Pages2302-2307
Number of pages6
DOIs
StatePublished - Dec 1 2011
Event2011 IEEE International Conference on Robotics and Automation, ICRA 2011 - Shanghai, China
Duration: May 9 2011May 13 2011

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729

Other

Other2011 IEEE International Conference on Robotics and Automation, ICRA 2011
CountryChina
CityShanghai
Period5/9/115/13/11

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'How many landmark colors are needed to avoid confusion in a polygon?'. Together they form a unique fingerprint.

Cite this