What, Why, How of the “Art-gallery Problem”
To put the problem statement in simple terms, Imagine that you are posed with the task to fix light bulbs to illuminate a room that is in the shape of a polygon with n vertices. Let us assume that the cameras have an infinite range and 360 degrees of visibility. Obviously, light cannot pass through a wall. Now try figuring out how many lights are needed to illuminate the whole polygon-shaped room. This is the whole crux of the art-gallery problem.
The problem gets rigorous when the various parameters like the light’s coverage, position, and nature of its environment come into the picture. More importantly, it very much essential to note that we want to find the minimum number of lights necessary for illuminating the whole polygon-shaped room.
One easy solution would be to place lights on all the edges or vertices of the polygon. But finding the minimum number of lights that are sufficient to illuminate the room is what we are looking for. In some cases, as shown below, placing bulbs in all the vertices or edges is not a wise option:
But in some cases like below, it might even help a bit
