
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.
Figure 7: Data structure for keeping 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 halfedges 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.
