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 <O(i)<. 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
2
n
3
n
4
n