The Voronoi Diagram

The voronoi diagram, also called the thiessen or dirichlet tessellation, has applications in many fields, from computer vision to archaeology. The technical definition is as follows:

Let P be a set of points in the plane. The Voronoi polygon containing p P is the set of all points x in the plane for which the distance from x to p is smaller than or equal to the distance from x to q, for all other points q in P.

A non-technical definition might go as follows. Imagine a set of cities, situated at a set of points P. Each city has its own king. Suppose now peasants in the countryside all pledge their loyalty to the king of the nearest city. If a cartographer were to draw a map of the land, where would the borders of the kingdoms be? The cartographer would end up drawing the voronoi diagram of the cities. In fact, archaeologists have used this very technique to approximate the boundaries of ancient civilizations.

The DotPlacer Applet (on this site) allows you to place a set of points on the screen, and have it draw the voronoi diagram for you. You can even move the points around, and watch the diagram change. Try it!

I used the following algorithm to draw the voronoi diagram. First of all, for each set of three points, I calculate the orthocentre of the three points. That is, I calculate the point which is equidistant from all three points. Then, for each orthocentre x, I check all the points in P, to make sure that the three points used to find x are the three closest points of P to x. If they are not, I reject x from consideration. It is not needed to draw the voronoi diagram.

Then, for each orthocentre x not rejected, I find another orthocentre y which "matches" x in the sense that it if x is the orthocentre of pi, pj and pk, then y is the orthocentre of two of these three points (and another point from P). If matches yij, yjk and yki are found for x, I draw a line between x and y. Otherwise, suppose there was no match yij sharing pi and pj with x. Then I draw a ray from x, perpendicular to the line between pi and pj. Roughly speaking, that's the algorithm I use.

This algorithm is certainly not the most efficient one available for constructing the voronoi diagram, but it works.

The voronoi diagram is very closely related to the delauney triangulation. This being the case, the same calculations used to construct the voronoi diagram are also used to draw the delauney triangulation.

For more information on the voronoi diagram, see this World of Mathematics article. r perhaps you'd like a solid text on the subject? Clicking the book on the left will allow you to get one that covers Voronoi diagrams, and other topcis, in depth. The book on the right, with code samples and good explanations, is regarded by many as one of the best books around for applying java (and smalltalk) to numerical methods. Enjoy!

Perhaps you'd like to read about the time I calculated some of the Voronoi diagram of the Ulam Prime Spiral?

File translated from TEX by TTH, version 2.25.