We then show that our results extend to k trees. Since the degree of p i 2 has not been changed, the algorithm proceeds as in the case of inductive hypothesis and thus produces a legal coloration.
Interior walls are non intersecting interior diagonals connecting some pairs of vertices.
We should add that it is tempting to place a light on every third vertex of the polygon. The reader can easily design a gallery where this placement strategy will fail no matter on which vertex one starts placing the lights. The problems of decomposing simple polygons into various types of more structured polygons have a number of practical applications and have received considerable attention recently from the theoretical perspective. The problems of decomposing simple polygons into various types of more structured polygons have a number of practical applications and have received considerable attention recently from the theoretical perspective. D. Avis and G.T. Toussaint.