How many landmark colors are needed to avoid confusion in a polygon?
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.
Lawrence H. Erickson Steven M. LaValle
Department of Computer Science University of Illinois at Urbana-Champaign Urbana,IL 61801 USA
国际会议
2011 IEEE International Conference on Robotics and Automation(2011年IEEE世界机器人与自动化大会 ICRA 2011)
上海
英文
2302-2307
2011-05-09（万方平台首次上网日期，不代表论文的发表时间）