Polygon Triangulation: the "Art Gallery" problem
|
The "art gallery problem" asks the question: how many guards (or cameras) does it take to guard an art gallery; that is, how many cameras do you need to be sure you can watch every wall of the gallery?
The solution to this problem begins with the triangulation of a polygon. We use here a recursive algorithm for triangulating the polygon, which is also shown elsewhere: connect two vertices with a diagonal which lies totally within the polygon; this decomposes the polygon into two smaller polygons. Recursively continue until all the smaller polygons are triangles. If an art gallery can be an arbitrary polygon (each side is a wall of the gallery), then we can guard the gallery if we can guard each triangle formed from a triangulation of the gallery (polygon). A triangle can always be guarded by one camera at any of its vertices. Therefore, we need to try to find how few vertices we need for cameras in order to guard every triangle. After triangulating the polygon, we convert the triangulation into its dual: a graph for which each node represents a triangle, and each edge represents a shared side of the triangulation. We can traverse the dual graph of the triangulated polygon, coloring the vertices of each triangle as we go. We will only need three colors. Then we can see which color was used least often; the vertices with this color are where we should put our cameras or guards. This work was done, wholly or in part, by Anne Fairchild Peacock, F&M '02. Click on the Download button at the right to download a zipped file of all movies described on this page. |