# Map-Coloring the Interior Regions Defined by the Diagonals of a Regular Polygon

Map-Coloring the Interior Regions Defined by the Diagonals of a Regular Polygon

Graph-coloring the interior regions determined by the diagonals of a regular polygon is a simply stated but deceptively complex problem. Given a polygon with sides, the number of diagonals increases at a rate between and . The number of intersections between diagonals and the number of interior regions increase at a super-cubic rate . The interior regions formed by the diagonals constitute a planar graph, but it is not the polygonization given by a Delaunay triangulation. This Demonstration presents the methods of exploiting and refining the Delaunay plane-sweep algorithm, obtaining and coloring the dual graph of a polygon mesh.

n

n

n

2

n<O(i)<n

3

4