The Computation of the Voronoi Diagram of a Circle Set Using the Voronoi Diagram of a Point Set: II. Geometry

An efficient and robust algorithm to compute the exact Voronoi diagram of a circle set is presented. The circles are located in a two dimensional Euclidean space, the radii of the circles are non-negative and not necessarily equal, and the circles are allowed to intersect each other. The idea of the algorithm is to use the topology of the point set Voronoi diagram as a seed so that the correct topology of the circle set Voronoi diagram can be obtained through a number of edge flipping operations. Then, the geometries of the Voronoi edges of the circle set Voronoi diagram are computed. In particular, this paper discusses the topological aspect of the algorithm, and the following paper discusses the geometrical aspect. The main advantages of the proposed algorithm are in its robustness, speed, and the simplicity in its concept as well as implementation. Since the algorithm is based on the result of the point set Voronoi diagram and the flipping operation is the only topological operation, the algorithm is always as stable as the Voronoi diagram construction algorithm of a point set.