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
But we are looking for a generic way to derive the minimum number of lights sufficient to illuminate a room with n-vertices. This is where the whole idea of min-over max formulation comes to play. Though it might be a bit confusing for beginners it is very frequently used in mathematics.
In 1975, A mathematician named Fisk came up with a proof that claimed that n/3 lights are sufficient to illuminate a polygon-shaped art gallery. His idea was to partition the polygon into triangles with diagonals.
A diagonal is a line segment that connects two vertices of a polygon without intersecting with its edges or other diagonals formed out of triangulation. A diagonal is legal only if it falls completely inside the considered polygon.
One very important lemma to remember in triangulation is that
The triangulation of a polygon P with n vertices uses n-3 diagonals and n-2 triangles.
Then the 3-coloring algorithm is applied on top of the triangulated polygon. Wherein a particular color among the chosen 3-colors is assigned to a node (i.e vertex) in such a way two connected nodes don’t share the same color. We then have to place lights on vertices that share any one particular color.
Now, fisk claims from his proof that placing lights in vertices that are either colored in red, green, or violet would be sufficient to illuminate the whole art gallery.
This art-gallery problem finds its application in a variety of domains like video game development, robot path planning, etc. The whole deal of visibility problems is being dealt with in this art-gallery problem. There are many variants to this art-gallery problem based on the posed constraints and nature of the environments. One could even find applications for this triangulation problem in day-to-day activities like sprinkler setup, cricket fielding setup, etc.
Though there are multiple algorithms to triangulate a polygon, I have shown only one implementation below which triangulates a polygon by ear clipping. This python program takes input from a file that contains vertices of the polygon in a cyclic manner. Do check out my GitHub repo for the complete implementation.
Results:-
References:-
- Computation geometry in C — Joesph O’Rourke
