2. Orthogonal polygons
Two natural outgrowths of the proof of the Chvátal Art Gallery Theorem were to see how the ideas in the proof could be extended to get more general results, and to see how the number of guards needed might change when working with polygons with special characteristics. More specifically, one line of research has concerned seeing whether special classes of polygons require fewer guards. For example, what can be said about simple polygons such as the one below, where all interior angles are either 90 degrees or 270 degrees? Such polygons are known as orthogonal polygons or rectilinear polygons.
Other orthogonal polygons, which are shown below, create rather different visual impressions:
Yet, you can verify that if one is allowed to locate a guard within the interior of an edge then only one guard is needed for each of the polygons in Figures 2 and 3. However, whereas Figure 2 can not be guarded by one guard located at a vertex, Figure 3 can. Below is a polygon which suggests a family of orthogonal polygons that needs an increasing number of vertex guards. Usingthe number of guards that are needed for the polygon in Figure 4, can you makea conjecture concerning how many vertex guards are sometimes necessary and alwayssufficient for an orthogonal polygon?