## Placing guards in an art gallery

Certain schools of modern architecture produce public buildings -- such as art galleries and museums -- which have rooms with irregular polygonal shapes. A theorem of V. Chvátal asserts that in any n-gonal room it is possible to arrange no more than n/3 guards so that every point of the room is seen by at least one of the guards. This project will provide a procedure which places the guards in the appropriate spot for any polygonal room. The project has three parts so that successful completion of the project will be worth two projects. Alternatively, only the first part can be completed for credit for one project.

First of all, it will be necessary to be able to produce a large number of polygonal rooms -- in other words, a procedure which produces random n-gions is necessary. At first glance it may seem that this is easy: Given an integer n as input, choose n rando points in the plane and connect them by straight lines. However, a moments reflection wil show that such a simple minded procedure will not always produce a polygon which could be used as a room since line my cross each other. Modify this procedure to creat a procedure which does produce random polygonal rooms. (Actually it would be more precise to say that such a procedure produces a seemingly random rooms because it is not even clear what is meant by a random polygonal room and this question will not be considered further.) Your procedure should choose succesive vertices of the polygon at random subject to the restriction that no two lines can intersect (except at designated vertices) and the last point must connect to the first point.

The second part of the project requires dividing a given polygon into triangles by connecting vertices with lines. Try to prove that this can always be done. If the polygon is convex then it is easy -- simply choose any vertex and then connect it to all the others. However, if the polygon is not convex then this will not always work. This can be done by induction though if it is possible to choose at leat one pair of vertices which can be connected with a straight line not intersecting any of the edges of the polygon. If this can be done then the polygon is divided into two smaller polygons and the induction hypothesis allows these to be divided into triangles as desired. This suggests that recursion can be used to write a procedure to do this. (However, why is there always a pair of vertices which can be connected by a straight line as desired?)

Having found the triangles, all that has to be done is to write a procedure which colours the vertices of th epolgon in thre colours so that each triangle has all three colours. Now one of the colours is only used on no more than n/3 vertices. Why does position guards at these vertices result in a placement so that each spot in the room is seen by at least one guard?

Juris Steprans