Department of
Applied
Mathematics

Chromatic art gallery problems for point and vertex guards

Subir Ghosh

Abstract

The art gallery problem is to determine the number of guards (or surveillance cameras) sufficient to cover or see every point in the interior of an art gallery. An art gallery can be viewed as a polygon P (with or without holes) with a total of n vertices, and guards as points in P. Any point z in P is said to be visible from a guard g if the line segment joining z and g does not intersect the exterior of P. This problem was first posed by Victor Klee in a conference in 1973, and in the course of time, it has become an important problem in computational geometry with extensive applications to surveillance of buildings like airport terminals, railway stations etc. A polygon is said to be guarded by a set of chosen guards if every interior point of P is visible from some guard within the guard set.

Chromatic art gallery problems arise from applications in areas like landmark-based robot navigation and wireless networks. One such problem is the weak-conflict free guarding of polygons, where the objective is to colour a chosen guard set S for P using the minimum number of colours such that each point within P sees at least one guard from S with an unique colour. Note that the objective here is to minimize the number of colors rather than the number of guards in S. We present an algorithm for weak conflict-free guarding of P (without holes) where the point guard set is coloured using only O(log n) colours.

Finally, we discuss a few open problems on weak conflict-free guarding of P for both point and vertex guards.