Voronoi Algorithms Página 1 de 5
Here is a list of all voronoi algorithms implemented in this applet, along with a short description and explanation.
Plane Intersect
This algorithm is the straightforward naive approach to generating a Voronoi diagram.
Motivation
The impulse is given by the mathematical description for genrating a Voronoi Cell, namely by merging all halfplanes generated
by the bisecting line between the site and all other sites in the plane.
V(pi) = merge i!=j H(pi, pj)
where H(pi, pj) is the halfplane between site i and site j.
Illustration
The basic principle is the following: Take each site in the plain, and determine the bisection line between the point and every
other point and unify all halfplanes thus created. This process must be repeated for each and every site in the plane.
Figure2 - A second halfplane is found and merged with the first
Figure1 - The first halfplane is found.
one.
Figure3 - A third halfplane is merged with the other Figure4 - The resulting edge of the merged planes defines the
two. Voronoi Cell.
Complexity
It is easy to see that the complexity in this case is O(n2).
Plane Sweep
After the naive approach in the previous algorithm, this one attempts to achieve some efficiency by cutting out some redundancy.
Motivation
The basic idea for this algorithm is the additional introduction of the concept of incremental generation. The diagram is generated
site by site, always inserting the last site into the diagram.
The methodology is as follows:
After the sites have been sorted along the increasing x-axis, in order to avoid inserting sites into the center, the first diagram is
generated. Afterwards the sites are subsequently inserted into the fringe of the diagram, minimizing necessary cutting operations.
Illustration
These steps show the start of a computation cycle, i.e. the first three sites in the sorted list.
http://www.cip.ifi.lmu.de/~viermetz/cg/Voronoi_Algorithms.html 12/16/2007
Voronoi Algorithms Página 2 de 5
Figure 2 - The first two are selected to generate the
Figure 1 - All sites are sorted by ascending x value.
simplest of all Voronoi diagrams.
Figure 3 - The third site is selected and added. The cell into Figure 4 - The bisector between the new site and it's
which it falls is determined. host is determined, the host cell is cut with this bisector.
Figure 5 - Through this cut in the last step, a neighbor cell of
Figure 6 - In this case, this stage of the generation is
the host cell has been affected, and a new bisector must also
finished.
be generated and inserted.
Complexity
The Complexity for this algorithm is:
Best case - O(n)
Worst case - O(n2)
Average - O(n logn)
Divide and Conquer
Another approach to increasing efficiency is the well known division and conquer method. As we have seen in the last algorithm,
it is quite possible and efficient to insert single sites into an already calculated Voronoi Diagram. This approach might be
generalized into the process of inserting not one site, but several sites already merged into a Voronoi Diagram.
Motivation
The algorithm is naturally divided into two steps:
Divide :
The sites in the plane are subsequently divided into two halves along a successively determined bisecting line.
Conquer:
The resulting binary tree with site in the leaves is successively merged into ever increasing Voronoi diagrams.
Illustrtion
Division: Two random sites are picked, and the sites divided along the generated bisector line. Each subset is further divided until
only two or less elements are left, constituting the two simplest possible of voronoi diagrams.
http://www.cip.ifi.lmu.de/~viermetz/cg/Voronoi_Algorithms.html 12/16/2007
Voronoi Algorithms Página 3 de 5
Figure 2 - The generated tree after division. Each node represents a
Figure 1 - The sites in the plane
bisector.
Conquer: The leaves of the tree are treated as finished Voronoi Diagrams. The interesting bit is the merging of two sepereate
Voronoi Diagrams representing the results of two subtrees.
Figure 1 - The two Voronoi sets to merge (blue and green). Figure 2 - Each cell(red) along the common border between
The yellow line is the bisector between the sets. the sets must now be clipped with its opposite member.
Figure 3 - The result for the first cell(red). Figure 4 - The result for the second cell(red).
Figure 5 - Merged sets.
Complexity
The complexity is determined by the two constituents of the algorithm:
Divide Step: O(n logn)
Conquer Step: O(n logn)
Total complexity is then, naturally, also O(n logn).
Fortune's Algorithm
http://www.cip.ifi.lmu.de/~viermetz/cg/Voronoi_Algorithms.html 12/16/2007
Voronoi Algorithms Página 4 de 5
After the previous two algorithms, which were constructed more according to general algorithm design principles, the following
algorithm was proposed by Fortune in 1985, improving upon the efficacy, and guaranteeing a worst case performance of O(n
logn).
Motivation
The efficacy inherent in the algorithm is constituted in the geometric assumptions from which the algorithm is derived. A cone
with 45 degree angle is constructed centered on each site in the plane. A slanted plane (45 degree angle) is now dragged across
the coordinate system. The intersection between the cones, when projected onto the x-y plane defines the voronoi lines. when the
angled plane moves across the x axis, the intersection of the plane with the individual cones, when projected onto the x-y plane
clearly defines the intersection points of the individual parabola curves, and thus the voronoi lines between the sites in the x-y
plane.
Illustration
Figure 1 - First all sites must translate into a Point Event
Figure 2 - When the sweepline passes a Point Event, a new
(red circles) where the plane intersects a new cone, and a
parabola must be created and inserted into the wavefront.
new parabola is created.
Figure 3 - During the execution of a Point Event, the future Figure 4 - At such coordinates a Circle Event (green circle)
intersection between two voronoi lines can be determined must be executed to remove the disappearing parabola and
(Circle Event - green circle). terminate the Voronoi Lines.
Complexity
Worst Case: O(n logn). Best Case: O(k * n).
Wave Front Visualization
This is not an algorithm per se, but a animation to simulate natural processes that generate designs as seen in Voronoi Diagrams,
such as crystal growth, or or maybe bacterium growth in a petri dish.
This algorithm also visually illustrates the intention of a voronoin diagram, and the defining property of enclosing all points
closer to one site in the plane in a voronoi cell.
http://www.cip.ifi.lmu.de/~viermetz/cg/Voronoi_Algorithms.html 12/16/2007
Voronoi Algorithms Página 5 de 5
http://www.cip.ifi.lmu.de/~viermetz/cg/Voronoi_Algorithms.html 12/16/2007
