IBDP MAI : Topic 3 Geometry and trigonometry - AHL 3.14 Graph theory Graphs, vertices, edges AI HL Paper 3
Question
This question models the planning of a new town and the location of a toxic waste dump in a metropolitan area.
A metropolitan area is modeled as a square. The area has four towns at its corners. All units are in kilometers, with the \( x \)-coordinate representing distance east and the \( y \)-coordinate distance north from the origin at \( (0, 0) \).
Edison is at \( E(0, 40) \), Fermitown at \( F(40, 40) \), Gaussville at \( G(40, 0) \), and Hamilton at \( H(0, 0) \).
(a) The model assumes each town is represented by a single point. Describe possible circumstances where this assumption is reasonable. [2]
(b) Sketch a Voronoi diagram showing the regions within the metropolitan area closest to each town. [3]
(c) The council plans to build a new town, Isaacopolis, at \( I(30, 20) \). A new Voronoi diagram includes Isaacopolis. The perpendicular bisector of \( [IE] \) is \( y = \dfrac{3}{2} x + \dfrac{15}{2} \).
(i) Find the equation of the perpendicular bisector of \( [IF] \). [2]
(ii) Given one vertex of the new Voronoi diagram is \( (20, 37.5) \), find the coordinates of the other two vertices within the metropolitan area. [3]
(iii) Sketch the new Voronoi diagram showing the regions closest to each town. [1]
(i) Find the equation of the perpendicular bisector of \( [IF] \). [2]
(ii) Given one vertex of the new Voronoi diagram is \( (20, 37.5) \), find the coordinates of the other two vertices within the metropolitan area. [3]
(iii) Sketch the new Voronoi diagram showing the regions closest to each town. [1]
(d) The metropolitan area is divided into districts based on the Voronoi regions from part (c). A car travels due east from a point due north of Hamilton to a point due north of Gaussville, passing through the Edison, Isaacopolis, and Fermitown districts. The car spends 30% of its travel time in the Isaacopolis district. Find the distance between Gaussville and the car’s destination point. [4]
(e) A toxic waste dump must be located within the metropolitan area, as far as possible from the nearest town.
(i) Find the location of the toxic waste dump, given it is not on the edge of the metropolitan area. [2]
(ii) State one possible criticism of the council’s choice of location. [1]
(i) Find the location of the toxic waste dump, given it is not on the edge of the metropolitan area. [2]
(ii) State one possible criticism of the council’s choice of location. [1]
(f) The toxic waste dump, \( T \), is connected to the towns via a sewer system, represented by matrix \( M \), with rows and columns ordered \( (E, F, G, H, I, T) \):
A leak from \( T \) travels through the sewers, taking one day per direct connection. A 1 in \( M \) indicates a direct connection, with 1s on the diagonal meaning a polluted location stays polluted.
(i) Identify which town is last to be polluted and justify your answer. [2]
(ii) State the number of days for the pollution to reach the last town. [1]
(iii) A sewer inspector needs the shortest route through each connection between different locations. Determine an appropriate start and end point for the inspection route, noting that self-connections do not require inspection. [2]
A leak from \( T \) travels through the sewers, taking one day per direct connection. A 1 in \( M \) indicates a direct connection, with 1s on the diagonal meaning a polluted location stays polluted.
(i) Identify which town is last to be polluted and justify your answer. [2]
(ii) State the number of days for the pollution to reach the last town. [1]
(iii) A sewer inspector needs the shortest route through each connection between different locations. Determine an appropriate start and end point for the inspection route, noting that self-connections do not require inspection. [2]
▶️ Answer/Explanation
Markscheme
(a)
Reasonable if:
(i) Towns are small compared to the 40 km distance between them. A1
(ii) Each town has an identifiable center (e.g., town hall) at the given coordinates. A1
[2 marks]
Reasonable if:
(i) Towns are small compared to the 40 km distance between them. A1
(ii) Each town has an identifiable center (e.g., town hall) at the given coordinates. A1
[2 marks]
(b)
Voronoi diagram: Perpendicular bisectors at \( x = 20 \), \( y = 20 \) divide the 40×40 square into four quadrants: E (top-left), F (top-right), G (bottom-right), H (bottom-left). M1 A1
A1
[3 marks]
Voronoi diagram: Perpendicular bisectors at \( x = 20 \), \( y = 20 \) divide the 40×40 square into four quadrants: E (top-left), F (top-right), G (bottom-right), H (bottom-left). M1 A1
A1 [3 marks]
(c)(i)
Points: \( I(30, 20) \), \( F(40, 40) \). Slope of IF: \( \dfrac{40 – 20}{40 – 30} = 2 \). M1
Perpendicular slope: \( -\dfrac{1}{2} \). Midpoint: \( \left( \dfrac{30 + 40}{2}, \dfrac{20 + 40}{2} \right) = (35, 30) \).
Equation: \( y – 30 = -\dfrac{1}{2} (x – 35) \), so \( y = -\dfrac{1}{2} x + 47.5 \). A1
[2 marks]
Points: \( I(30, 20) \), \( F(40, 40) \). Slope of IF: \( \dfrac{40 – 20}{40 – 30} = 2 \). M1
Perpendicular slope: \( -\dfrac{1}{2} \). Midpoint: \( \left( \dfrac{30 + 40}{2}, \dfrac{20 + 40}{2} \right) = (35, 30) \).
Equation: \( y – 30 = -\dfrac{1}{2} (x – 35) \), so \( y = -\dfrac{1}{2} x + 47.5 \). A1
[2 marks]
(c)(ii)
Vertex 1: \( (20, 37.5) \). Solve IE (\( y = \dfrac{3}{2} x + \dfrac{15}{2} \)) and IF (\( y = -\dfrac{1}{2} x + 47.5 \)): \( \dfrac{3}{2} x + \dfrac{15}{2} = -\dfrac{1}{2} x + 47.5 \), \( x = 20 \), \( y = 37.5 \). M1
Vertex 2: EH bisector (\( y = 20 \)), IE at \( y = 20 \): \( 20 = \dfrac{3}{2} x + \dfrac{15}{2} \), \( x = \dfrac{25}{3} \), so \( \left( \dfrac{25}{3}, 20 \right) \). A1
Vertex 3: FG, GH intersection at \( (20, 20) \). A1
[3 marks]
Vertex 1: \( (20, 37.5) \). Solve IE (\( y = \dfrac{3}{2} x + \dfrac{15}{2} \)) and IF (\( y = -\dfrac{1}{2} x + 47.5 \)): \( \dfrac{3}{2} x + \dfrac{15}{2} = -\dfrac{1}{2} x + 47.5 \), \( x = 20 \), \( y = 37.5 \). M1
Vertex 2: EH bisector (\( y = 20 \)), IE at \( y = 20 \): \( 20 = \dfrac{3}{2} x + \dfrac{15}{2} \), \( x = \dfrac{25}{3} \), so \( \left( \dfrac{25}{3}, 20 \right) \). A1
Vertex 3: FG, GH intersection at \( (20, 20) \). A1
[3 marks]
(c)(iii)
Bisectors: IE (\( y = \dfrac{3}{2} x + \dfrac{15}{2} \)), IF (\( y = -\dfrac{1}{2} x + 47.5 \)), EH (\( y = 20 \)), FG (\( y = 20 \)), GH (\( x = 20 \)). Regions defined by vertices \( (20, 37.5) \), \( \left( \dfrac{25}{3}, 20 \right) \), \( (20, 20) \).
A1
[1 mark]
Bisectors: IE (\( y = \dfrac{3}{2} x + \dfrac{15}{2} \)), IF (\( y = -\dfrac{1}{2} x + 47.5 \)), EH (\( y = 20 \)), FG (\( y = 20 \)), GH (\( x = 20 \)). Regions defined by vertices \( (20, 37.5) \), \( \left( \dfrac{25}{3}, 20 \right) \), \( (20, 20) \).
A1 [1 mark]
(d)
Path: From \( (0, k) \) to \( (40, k) \), distance 40 km. M1
Isaacopolis boundaries at \( y = k \): \( x = \dfrac{25}{3} \) (IE, EH) to \( x = 20 \) (IF, FG at \( k = 37.5 \)).
Distance in Isaacopolis: \( 20 – \dfrac{25}{3} = \dfrac{35}{3} \approx 11.67 \, \text{km} \). A1
Proportion: \( \dfrac{\dfrac{35}{3}}{40} \approx 0.2917 \approx 30\% \) at \( k = 37.5 \). A1
Distance from \( G(40, 0) \) to \( (40, 37.5) \): 37.5 km. A1
[4 marks]
Path: From \( (0, k) \) to \( (40, k) \), distance 40 km. M1
Isaacopolis boundaries at \( y = k \): \( x = \dfrac{25}{3} \) (IE, EH) to \( x = 20 \) (IF, FG at \( k = 37.5 \)).
Distance in Isaacopolis: \( 20 – \dfrac{25}{3} = \dfrac{35}{3} \approx 11.67 \, \text{km} \). A1
Proportion: \( \dfrac{\dfrac{35}{3}}{40} \approx 0.2917 \approx 30\% \) at \( k = 37.5 \). A1
Distance from \( G(40, 0) \) to \( (40, 37.5) \): 37.5 km. A1
[4 marks]
(e)(i)
Maximize minimum distance to towns. At \( (20, 20) \): distance to \( I(30, 20) \) is 10 km, to E, F, G, H is \( \sqrt{20^2 + 20^2} \approx 28.28 \, \text{km} \). M1
Location: \( (20, 20) \). A1
[2 marks]
Maximize minimum distance to towns. At \( (20, 20) \): distance to \( I(30, 20) \) is 10 km, to E, F, G, H is \( \sqrt{20^2 + 20^2} \approx 28.28 \, \text{km} \). M1
Location: \( (20, 20) \). A1
[2 marks]
(e)(ii)
Criticism: \( (20, 20) \) is only 10 km from Isaacopolis, posing potential health risks. A1
[1 mark]
Criticism: \( (20, 20) \) is only 10 km from Isaacopolis, posing potential health risks. A1
[1 mark]
(f)(i)
Matrix \( M \): T connects to E, F, G, H. Day 1: E, F, G, H polluted. Day 2: E, G, H to I. M1
Last town: Isaacopolis (I). A1
[2 marks]
Matrix \( M \): T connects to E, F, G, H. Day 1: E, F, G, H polluted. Day 2: E, G, H to I. M1
Last town: Isaacopolis (I). A1
[2 marks]
(f)(ii)
Time to I: 2 days. A1
[1 mark]
Time to I: 2 days. A1
[1 mark]
(f)(iii)
Edges: T-E, T-F, T-G, T-H, E-I, G-I, H-I. Degrees: F, I odd (1); others even. M1
Eulerian path: Start at F, end at I (or vice versa). A1
[2 marks]
Edges: T-E, T-F, T-G, T-H, E-I, G-I, H-I. Degrees: F, I odd (1); others even. M1
Eulerian path: Start at F, end at I (or vice versa). A1
[2 marks]
Total Marks: 23