Adding a site: the incremental algorithm Problem set A

The diagram shows the Voronoi diagram for the sites A, B, C and D. A new site E is added at (4, 5).

1. (a) Write down the sites that share an edge with E in the new diagram.
2. (b) Find the equation of the perpendicular bisector of E and D.
3. (c) Find the coordinates of the vertices of the new cell around E.

The diagram shows the Voronoi diagram for the sites A, B, C and D. A new site E is added at (6, 2).

1. (a) One vertex of the old diagram is not a vertex of the new diagram. Write down its coordinates and show that it is nearer to E than to the sites it was equidistant from.
2. (b) How many edges does the new cell around E have?

The diagram shows the Voronoi diagram for the sites A, B, C and D in a rectangular region. A new site E is added at (6, 1), and its cell reaches the edge of the region.

1. (a) Find the equation of the perpendicular bisector of E and A.
2. (b) Write down the coordinates of the points where the edges of the new cell meet the boundary of the region.

A town has four supermarkets. Customers go to the nearest supermarket. The diagram shows the Voronoi diagram for the four existing supermarkets, with a new supermarket E that opens at (2, 5). One unit on each axis is 1 km.

1. (a) Find the coordinates of the vertices of the new cell around E.
2. (b) Find the greatest distance from E to a vertex of its cell.

A city has five post offices. The diagram shows the Voronoi diagram for the five existing post offices. A new post office F opens at (6, 3).

1. (a) Which existing post offices lose part of their cell when F is added?
2. (b) Which existing post offices keep exactly the same cell?

A town has four libraries, A(5, 1), B(2, 7), C(1, 5) and E(2, 5), where the units are kilometres. The diagram shows the Voronoi diagram. The library at E closes.

1. (a) Find the coordinates of the vertex where the cells of the three remaining sites meet.
2. (b) Write down the coordinates of the vertices that are removed from the diagram.

Three Wi-Fi routers A, B and C are in a hall. Two more routers, D and then E, are installed one at a time, and each device connects to the nearest router. The diagram shows the Voronoi diagram for A, B and C, and the positions of D and E. One unit on each axis is 1 m.

1. (a) Find the coordinates of the vertices of the cell around D after D is added. Include any corner of the region in the cell, and any point where its edges meet the boundary.
2. (b) Find the coordinates of the vertices of the cell around E after E is added to the diagram for A, B, C and D.

A county has four hospitals. The diagram shows the Voronoi diagram for the four existing hospitals. A new one, E, opens at (6, 3). Two of the existing hospitals that shared an edge before no longer share an edge. Which two, and why?