Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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

Best regards,
- Doctor Floor, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Euclidean Geometry
High School Euclidean/Plane Geometry

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search