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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.