In computing the plane the intervals in the tangent line (see the Circle example) become circles. Circles are trimmed by removing half-planes. This creates polygons, beginning with squares slightly larger than the circle (red edges). If all of the vertices of the polygon lie inside the circle there is no boundary of the circle left in the collection of circles. If a vertex lies outside the circle, a line joing the center of the circle to the vertex crosses the circle at a boundary point (yellow).

The blue edges are the dual of the polygons. This is roughly analogous to the Delaunay triangulation of the points.

In this example the circles are all the same size. The algorithm does not require this.

Anyone know of an implementation of the coloring that the four color theorem assures us exists?

[Research home page]

[ **IBM home page** |
**Order** |
**Privacy** |
**ContactIBM** |
**Legal** ]