13.02 Voronoi diagrams

Voronoi diagrams divide an area into certain regions in which the points are closest to the site within that region:

So in the above example, all the points in the region with site $A$A are closer to site $A$A than any other site ($B$B to $G$G) on the diagram. The region with site $A$A is called a cell, and the lines between the cells are called edges. The point where two or more edges meet is called a vertex.

The points on an edge are equidistant from the two sites that that the edge lies between. So if you consider the edge between the two regions for sites $B$B and $D$D in the above example, each point along this straight line has the same distance from $B$B as it does from $D$D.

A vertex is equidistant to all sites that the vertex lies between. So if you consider the vertex between the three regions for sites $A,B$A,B and $G$G in the above example, this vertex has the same distance from $A$A as it does from $B$B and from $G$G.

 

Worked example

example 1

Consider the following Voronoi Diagram for sites $X,Y$X,Y and $Z$Z:

(a) State a point in cell $X$X.

(b) What can be said about the vertex?

(c) Which site(s) is the point $(1,1)$(1,1)  closest to?

(d) Which site(s) is the point $(2,-3)$(2,−3)  closest to?

 

 

(a)
Think: We can choose any of the points in the area around site $X$X that is in the top left region. 

Do: Possible answers include: $(-2,0),(-4,1),(-3,5),(-5.2,-1)$(−2,0),(−4,1),(−3,5),(−5.2,−1) 

(b) 

Think: There is only one vertex between the three regions.

Do: Therefore, this point is equidistant between $X,Y$X,Y and $Z$Z.

(c) 

Think:  $(1,1)$(1,1) is in the cell about site $Y$Y. 

Do:  $(1,1)$(1,1) is closest to site $Y$Y.

(d)

Think:  $(2,-3)$(2,−3)  is on the edge between sites $Y$Y and $Z$Z. So it is equidistant to both sites.

Do:   $(2,-3)$(2,−3) is closest to site $Y$Y and site $Z$Z.