Sign in to jmaths to print this page or save it as a PDF: jmaths-8ce638778fd6.herokuapp.com/maths/ai-hl/voronoi-diagrams/12-8-4/problems/b/

jmaths

IB Mathematics: Applications and Interpretation HL · 12.8: Voronoi Diagrams · 12.8.4

Name Date

Adding a site: the incremental algorithm Problem set B

Draw the new cell on a copy of the diagram. Show the equations or distances that decide each edge and vertex.

Each question matches the question with the same number in set A. Do the ones you got wrong there.

Difficulty: first skills applying them stretch

Skills

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

    1234567891234567xyABCDE
    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 C.
    3. (c) Find the coordinates of the vertices of the new cell around E.

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

    1234567891234567xyABCDE
    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?

  3. 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 (5, 4), and its cell reaches the edge of the region.

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

In context

  1. A beach has four lifeguard towers. A swimmer in trouble is helped from the nearest tower. The diagram shows the Voronoi diagram for the four existing lifeguard towers, with a new tower E that opens at (2, 3). One unit on each axis is 1 km.

    1234567891234567xyABCDE
    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.

  2. A region has five fire stations. The diagram shows the Voronoi diagram for the five existing fire stations. A new fire station F opens at (7, 5).

    1234567891234567xyABCDEF
    1. (a) Which existing fire stations lose part of their cell when F is added?
    2. (b) Which existing fire stations keep exactly the same cell?

  3. A city has four ambulance stations, A(3, 4), B(5, 2), C(1, 2) and E(3, 3), where the units are kilometres. The diagram shows the Voronoi diagram. The station at E is shut for repairs.

    1234567891012345678xyABCE
    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.

Stretch

  1. Three cafés A, B and C are on a university campus. Two more cafés, D and then E, open one at a time, and each student goes to the nearest café. 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 km.

    1234567891234567xyABCDE
    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.

  2. A national park has four ranger stations. The diagram shows the Voronoi diagram for the four existing ranger stations. A new one, E, opens at (4, 3). Two of the existing ranger stations that shared an edge before no longer share an edge. Which two, and why?

    1234567891234567xyABCDE

jmaths.xyz · AI HL · 12.8.4 Adding a site: the incremental algorithm