Voronoi Diagrams

Date: 12/12/2000 at 03:46:12
From: Karl
Subject: Voronoi diagram

On a Voronoi diagram, how do you know which lines you need, and which 
parts of those lines you need?

We have already searched on many sites and in our math book.

Date: 12/13/2000 at 11:54:20
From: Doctor Floor
Subject: Re: Voronoi diagram
Hi, Karl,

Thanks for your question.

Using the following figure I will try to explain how to make a Voronoi 
cell, and which lines have to be used:

  

We start with a figure of six points ABCDE (F comes later). To 
construct the Voronoi cell of A, we draw the perpendicular bisectors 
of segments AB, AC, AD, and AE. These perpendicular bisectors enclose 
a polygon around point A. In the figure above this polygon is the bold 
black quadrilateral. Only the sides of this polygon form the cell 
around A. The rest can be removed (as is done in the figure).

You might ask: But if instead of the four points BCDE above, you have 
say, 20 points outside A, do you then have to draw all 20 
perpendicular bisectors?

That is not necessary. You can pick some points close to A, let's say 
B, C, D, and E. Draw the lines through these four points perpendicular 
to AB, AC, AD, and AE, respectively. In the earlier figure this gives 
the red dotted polygon, in this case a quadrilateral. Points inside 
this polygon have to be used to draw perpendicular bisectors, but 
points outside this polygon can be discarded.

So here is the reason why F is in the figure: F is outside the red 
dotted quadrilateral, and thus the perpendicular bisector of AF does 
not have to be drawn to create the Voronoi cell of A.

To read more more about Voronoi Diagrams, see Geometry in Action, a 
collection of applications of computational geometry by David 
Eppstein, Theory Group, ICS, UC Irvine:

  http://www.ics.uci.edu/~eppstein/gina/voronoi.html   

I hope this answers your question. If you have more questions, or if 
things in my reply are unclear, please write back. 

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/