Data structure for storing Voronoi diagram is combined from three data structures. Voronoi diagram consists of Voronoi cells (faces), Voronoi edges and Voronoi points [BERG97]. Each group of these elements is stored in its own data structure that are, of course, connected among them. Figure 7 is shown the graphical representation of the Voronoi diagram.
Let us just consider the final tasks of constructing the Voronoi diagram after all input points have been processed. The intersection points of half-edges with the box surrounding the Voronoi diagram are calculated. These points are proclaimed as the Voronoi points. This is done by help of the leaves of parabolic front tree, which stay in the tree after all events have been processed. Those leaves, which stay in the tree, represent exactly those Voronoi edges, which are not defined completely after the construction is done.
Roman Cuk - roman.cuk@uni-mb.si