http://goanna.cs.rmit.edu.au/~gl/classes/TriangulationApplet.java

comments included are:

1. Edge class. Edges have two vertices, s and t, and two faces,
l (left) and r (right). The triangulation representation and
the Delaunay triangulation algorithms require edges.

2. Circle class. Circles are fundamental to computation of

Delaunay triangulations. In particular, an operation which

computes a circle defined by three points is required.

3. Triangulation class. A triangulation is represented as a set

of points and the edges which form the triangulation.

4.


http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html#alg

Algorithms for Computing Voronoi Diagrams
-----------------------------------------------------------------

---------------

There are literally hundreds of different algorithms for

constructing various types of Voronoi diagrams. I will describe

two of the simplest.

The first algorithm inserts the points one at a time into the

diagram. Whenever a new point comes in, we need to do three

things. First, we need to figure out which of the existing Voronoi

cells contains the new site. Second, we need to "walk around" the

boundary of the new site's Voronoi region, inserting new edges

into the diagram. Finally, we delete all the old edges sticking

into the new region.

The second and third steps are the harder ones. It's possible that

each new site's Voronoi cell will touch all the old cells. Thus,

in the worst case, we end up spending linear time on each cell, or

O(n2) time overall. However, it has been proven that if you insert

the points in random order, the expected time is only O(n log n),

regardless of which set of points we're given. A divide and

conquer algorithm for constructing Voronoi diagrams was discovered

by Shamos and Hoey. Split the points into two halves, the leftmost

n/2 points, which we'll color bLue, and the rightmost n/2 points,

which we'll color Red. Recursively compute the Voronio diagram of

the two halves. Finally, merge the two diagrams by finding the

edges that separate the bLue points from the Red points The last

step can be done in linear time by the "walking ant" method. An

ant starts down at -infinity, walking upward along the path

halfway between some blue point and some red point. The ant wants

to walk all the way up to +infinity, staying as far away from the

points as possible. Whenever the ant gets to a red Voronoi edge,

it turns away from the new red point. Whenever it hits a blue

edge, it turns away from the new blue point. There are a few

surprisingly difficult details left to deal with, like how does

the ant know where to start, and how do you know which edge the

ant will hit next. (The interested reader is strongly encouraged

to consult the standard computational geometry literature for

solutions to these details.)


Delaunay Triangulations
-----------------------------------------------------------------

---------------

The Delaunay triangulation is the dual of the Voronoi diagram. To

build the Delaunay triangulation, draw a line segment between any

two sites whose Voronoi regions share an edge. This procedure

splits the convex hull of the sites into triangles.

The Delaunay triangulation has a number of nice properties. For

example, each point is connected to its nearest neighbor by an

edge in the triangulation. Since the Delaunay triangulation is a

planar graph, it has at most 3n-6 edges, where n is the number of

sites. So once you have the Dealunay triangulation, if you want to

find the closest pair of sites, you only have to look at 3n-6

pairs, instead of all n(n-1)/2 possible pairs.

Here are some nice properties of the Delaunay triangulation:



It's dual to the Voronoi diagram, so computing one automatically

gives you the other.

The Empty Circle Property -- If you draw a circle through the

vertices of ANY Delaunay triangle, no other sites will be inside

that circle.

It's a planar graph. By Euler's formula, it has at most 3n-6 edges

and at most 2n-5 triangles. This property can be used to reduce

many problems with quadratic size (like closest pair) down to

linear size in the time it takes to construct the triangulation.

It contains "fat" triangles, in the sense that the minimum angle

of any Delaunay triangle is as large as possible. In fact, if you

write down the list of all angles in the Delaunay triangulation,

in increasing order, then do the same thing for any other

triangulation of the same set of points, the Delaunay list is

guaranteed to be lexicographically smaller.