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

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?

email address: steprans@mathstat.yorku.ca

Department of Mathematics and Statistics.

Ross 536 North, ext. 33921

York University