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
[Research home page]
[ IBM home page |