The Voronoi diagram below shows the hospitals A, B and C in a city:

The point marked D is a new hospital being built. We need to update the Voronoi diagram to include a cell corresponding to site D.

The new site currently lies in cell B, so some areas which were previously closest to hospital B will now be closest to hospital D.

In order to construct the border between cell B and cell D, we need to draw the perpendicular PB(B,D), which will meet PB(A,B) at point V (see below):

V is equidistant from A, B and D, so is a vertex of the new Voronoi diagram. So we add PB(A,D) to the diagram, starting from V as shown below. As this line doesn’t meet any other existing edges, no more vertices are created, hence this completes the construction of cell D:

To finish the diagram we remove the part of the existing edge PB(A,B) which now lies within cell D.

The step-by-step algorithm is outlined below:

• Step 1: Identify the site P_i, whose cell contains the new contains the new site X. Construct PB(P_i,X) within this cell. At any point where this line meets an existing edge, create a new vertex.
• Step 2: For each site P_j, whose cell is adjacent to a new vertx, construct PB(P_j,X) within that cell through the vertex. Continue creating new vertices as in step 1. Repeat this process until no more new vertices are created. At this time cell X is complete.
• Step 3: Remove any segments of edges from the original Voronoi diagram which now lie within cell X.

Worked Example

Redraw the Voronoi diagram below with an additional stie at E(-1,1):

Exercise

Answers