TY - GEN

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

AU - Erickson, Lawrence H.

AU - La Valle, Steven M.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84871685569&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84871685569&partnerID=8YFLogxK

U2 - 10.1109/ICRA.2011.5979838

DO - 10.1109/ICRA.2011.5979838

M3 - Conference contribution

AN - SCOPUS:84871685569

SN - 9781612843865

T3 - Proceedings - IEEE International Conference on Robotics and Automation

SP - 2302

EP - 2307

BT - 2011 IEEE International Conference on Robotics and Automation, ICRA 2011

T2 - 2011 IEEE International Conference on Robotics and Automation, ICRA 2011

Y2 - 9 May 2011 through 13 May 2011

ER -