Math and Logic

Convexity Complexity

Welcome to another hypothetical art gallery tour. Today's tour will feature convexity.

A figure has convexity if all of its interior angles are less than 180180^\circ. This way of thinking about things focuses our attention on the edges of the figure rather than the interior. What if we think about convexity in terms of line of sight instead?

In yesterday's problem we tried to place a guard in an art gallery inside a polygon so that every part of the interior could be "seen." We saw that three different concave (i.e. not convex) shapes can have different solutions. While A, B, and C are all concave, two of them can be guarded by a single person, but it's impossible for any one guard to see all of B from inside.

It turns out if we want art gallery problems to be interesting, they must be made with concave figures, because every convex polygon can be guarded by a single guard standing anywhere. If you're not convinced, consider that the inside of a convex gallery never has a corner that can block your view.

Saying that convex galleries only need one guard is just another way of stating a fundamental property of convex polygons: any vertex can be connected with any other without passing through one of the sides. This property is always true for convex polygons and it's always false for concave polygons (see the image above for an example).

This property is important for art gallery problems because a guard's line of sight is constrained by all the lines between the guard's position and the vertices of the gallery.

Some concave galleries, like A and C above, only need a single guard. Others, like B, need more. What makes these shapes different? Today's problem is a first step toward classifying galleries. Does the condition below always put a concave gallery in the "one-guard" category?

Today's Challenge

True or False?

Some simple polygonal galleries formed by overlapping three rectangles will require at least three guards.

Note: A gallery is guarded if every part of the gallery is in the line of sight of a guard.


Problem Loading...

Note Loading...

Set Loading...