An Art Gallery Approach to Ensuring that Landmarks are Distinguishable
Lawrence H. Erickson, Steven M. LaValle · 2011
How many different classes of partially distinguishable landmarks are needed to ensure that a robot can always see a landmark without simultaneously seeing two of the same class?To study this, we introduce the chromatic art gallery problem.A guard set S ⊂ P is a set of points in a polygon P such that for all p ∈ P , there exists an s ∈ S such that s and p are mutually visible.Suppose that two members of a finite guard set S ⊂ P must be given different colors if their visible regions overlap.What is the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of a polygon P ?We call this number, χG(P ), the chromatic guard number of P .We believe this problem has never been examined before, and it has potential applications to robotics, surveillance, sensor networks, and other areas.We show that for any spiral polygon Pspi, χG(Pspi) ≤ 2, and for any staircase polygon (strictly monotone orthogonal polygon) Psta, χG(Psta) ≤ 3.For lower bounds, we construct a polygon with 4k vertices that requires k colors.We also show that for any positive integer k, there exists a monotone polygon M k with 3k 2 vertices such that χG(M k ) ≥ k, and for any odd integer k, there exists an orthogonal polygon R k with 4k 2 + 10k + 10 vertices such that χG(R k ) ≥ k.