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?
home page ]