Planar Graphs · Special Layouts
Lesson 4
Below is the answer to the problem about the minimum number of light sources.
Let's now show what answers the algorithm will produce. The colored triangulations clearly demonstrate that it is enough to place light sources at the blue vertices.
For the curious 🤓
An attentive reader will notice that for the third room our algorithm finds two light sources, while the whole room can be lit with just one source (as shown above). At the same time, the theorem does not claim that the algorithm finds the optimal number of sources. In general, finding the optimal number of sources is a computationally hard problem.