Voronoi diagrams

a) The midpoint of $BC$ is $M=\left(\frac{7+3}{2},\frac{2+6}{2}\right)=(5,4)$. The gradient of $BC$ is $\frac{6-2}{3-7}=-1$, so the gradient of the perpendicular bisector is $1$. The line is $y-4=1\cdot (x-5)$, that is, $y=x-1$.

b) The perpendicular bisector of $A$ and $B$ is vertical, because $AB$ is horizontal: it passes through the midpoint $(4,2)$, so it is $x=4$. Intersecting it with $y=x-1$ gives $y=4-1=3$. The vertex is $V(4,3)$. As a check, the perpendicular bisector of $AC$ (midpoint $(2,4)$, gradient $-\frac{1}{2}$) is $y=-\frac{1}{2}x+5$, and at $x=4$ it gives $y=3$: it passes through $V$.

c) $VA=\sqrt{(4-1{)}^2+(3-2{)}^2}=\sqrt{10}$. Likewise $VB=\sqrt{3^2+1^2}=\sqrt{10}$ and $VC=\sqrt{1^2+3^2}=\sqrt{10}$. The distance is $\sqrt{10}\approx 3.16$ km.

d) Compare the distances: $PA=\sqrt{4^2+3^2}=5$, $PB=\sqrt{2^2+3^2}=\sqrt{13}\approx 3.61$ and $PC=\sqrt{2^2+1^2}=\sqrt{5}\approx 2.24$. The nearest is $C$. This is confirmed by the diagram: $P$ lies above the line $y=x-1$ (because $5>5-1$), on the side of $C$.

[FIGURA mai-t4-a5-ejemplo1: x window from 0 to 8, y from 0 to 8, with a grid. Sites A(1, 2), B(7, 2) and C(3, 6) marked with a dot and letter. Vertex V(4, 3) marked with a highlighted dot and the label V(4, 3). Three thick edges leaving V: vertical x = 4 downwards to (4, 0); the perpendicular bisector of AC, y = -0.5x + 5, upwards and to the left to (0, 5); the perpendicular bisector of BC, y = x - 1, upwards and to the right to (8, 7). The three cells coloured in soft tones: cell of A on the left, cell of B on the right and below, cell of C on top. Point P(5, 5) marked with a cross and the label P, inside the cell of C.]

a) The midpoint of $AC$ is $M=(25,30)$. The gradient of $AC$ is $\frac{50-10}{40-10}=\frac{4}{3}$, so the gradient of the perpendicular bisector is $-\frac{3}{4}$. The line is $y-30=-\frac{3}{4}(x-25)$, which gives $y=-\frac{3}{4}x+\frac{195}{4}$ (that is, $y=-0.75x+48.75$).

b) $A$ and $B$ are at the same height, so their perpendicular bisector is vertical and passes through the midpoint $(40,10)$: it is $x=40$. Substituting into the perpendicular bisector of $AC$: $$y=-\frac{3}{4}\cdot 40+\frac{195}{4}=-30+\frac{195}{4}=\frac{75}{4}=18.75$$ The vertex is $V\left(40,\frac{75}{4}\right)=(40;18.75)$. It is the only vertex: with three sites there is only one.

c) Distance to $A$: $\sqrt{(40-10{)}^2+(18.75-10{)}^2}=\sqrt{900+76.5625}=\sqrt{976.5625}=31.25$ km. To $C$: $\sqrt{0^2+(50-18.75{)}^2}=31.25$ km, and to $B$ it is the same by symmetry. The dump is 31.25 km from each of the three villages.

[FIGURA mai-t4-a5-ejemplo2: x window from 0 to 80 and y from 0 to 60 (rectangular area), with a grid every 10 units. Villages A(10, 10), B(70, 10) and C(40, 50) with dot and letter. Vertex V(40; 18.75) marked with a square or highlighted symbol and the label “Dump V(40; 18.75)”. Three thick edges leaving V: x = 40 downwards to (40, 0); the perpendicular bisector of AC, y = -0.75x + 48.75, upwards and to the left to (0; 48.75); the perpendicular bisector of BC, y = 0.75x - 11.25, upwards and to the right to (80; 48.75). Three cells coloured in soft tones: cell of A (left), cell of B (right) and cell of C (top). Thin dashed segments from V to A, to B and to C, with the label 31.25 km on one of them.]

a) $AB$ is horizontal, so its perpendicular bisector is $x=5$. For $AC$: midpoint $(3.5;4)$, and the gradient of $AC$ is $\frac{6}{3}=2$, so the gradient of the perpendicular bisector is $-\frac{1}{2}$, hence $y-4=-\frac{1}{2}(x-3.5)$. At $x=5$: $$y=4-\frac{1}{2}\cdot 1.5=\frac{13}{4}$$ The vertex is $V\left(5,\frac{13}{4}\right)=(5;3.25)$, at a distance of $3.25+\dots$ from the sites: $VA=\sqrt{3^2+2.25^2}=3.75$ (and the same for $B$ and $C$).

b) No. The distance from $V$ to $D$ is $|4-3.25|=0.75$, much smaller than $3.75$. So $V$ is closer to $D$ than to $A$, $B$ and $C$, and a vertex must be equidistant from three sites with no other site closer. Therefore $V$ disappears and lies inside the cell of $D$.

c) The vertices are points equidistant from three sites with no other site closer. We look for the perpendicular bisectors involving $D$:

• $AD$: midpoint $(3.5;2.5)$, and the gradient of $AD$ is $\frac{3}{3}=1$, so the perpendicular bisector is $y=-x+6$.
• $BD$: midpoint $(6.5;2.5)$, and the gradient of $BD$ is $-1$, so the perpendicular bisector is $y=x-4$.
• $CD$: $C$ and $D$ have the same $x$-coordinate, so the perpendicular bisector is horizontal through the midpoint $(5;5.5)$: $y=5.5$.
• $BC$: midpoint $(6.5;4)$, gradient $-2$, perpendicular bisector $y=\frac{1}{2}x+\frac{3}{4}$. By symmetry, $AC$ is $y=-\frac{1}{2}x+\frac{23}{4}$.

The intersections are: $x=5$ with $y=-x+6$ gives $(5,1)$ (equidistant from $A$, $B$ and $D$: $VA=VB=VD=3$); $y=-x+6$ with $y=5.5$ gives $x=\frac{1}{2}$, that is $\left(\frac{1}{2},\frac{11}{2}\right)$ (equidistant from $A$, $C$ and $D$); $y=x-4$ with $y=5.5$ gives $\left(\frac{19}{2},\frac{11}{2}\right)$ (equidistant from $B$, $C$ and $D$). In all three cases no other site is closer. The vertices are $(5,1)$, $(0.5;5.5)$ and $(9.5;5.5)$.

d) $PA=\sqrt{1^2+4^2}=\sqrt{17}$, $PB=\sqrt{5^2+4^2}=\sqrt{41}$, $PC=\sqrt{2^2+2^2}=\sqrt{8}$ and $PD=\sqrt{2^2+1^2}=\sqrt{5}$. The smallest is $PD$: the nearest station is $D$. This matches the diagram: $P$ lies below the edge $y=5.5$ and on the same side as $D$ of the edges $y=-x+6$ and $y=x-4$, so it is inside the cell of $D$.

[FIGURA mai-t4-a5-ej3-antes: x window from 0 to 10, y from 0 to 9, with a grid. Sites A(2, 1), B(8, 1) and C(5, 7) with dot and letter. Vertex V(5; 3.25) highlighted and labelled. Three thick edges leaving V: x = 5 downwards to (5, 0); the perpendicular bisector of AC, y = -0.5x + 5.75, to (0; 5.75); the perpendicular bisector of BC, y = 0.5x + 0.75, to (10; 5.75). Three cells coloured in soft tones: A on the left, B on the right, C at the top.]

[FIGURA mai-t4-a5-ej3-despues: same window (x from 0 to 10, y from 0 to 9). Sites A(2, 1), B(8, 1), C(5, 7) and the new site D(5, 4), the last one in a different colour and labelled “new D”. Thick edges: x = 5 from (5, 0) to the vertex (5, 1); y = -x + 6 from (5, 1) to the vertex (0.5; 5.5); y = x - 4 from (5, 1) to the vertex (9.5; 5.5); the horizontal y = 5.5 from (0.5; 5.5) to (9.5; 5.5); the perpendicular bisector of AC, y = -0.5x + 5.75, from (0.5; 5.5) to (0; 5.75) on the left edge; the perpendicular bisector of BC, y = 0.5x + 0.75, from (9.5; 5.5) to (10; 5.75) on the right edge. Vertices marked with a dot and their coordinates: (5, 1), (0.5; 5.5) and (9.5; 5.5). The four cells coloured in soft tones: A on the left, B on the right, D in the centre (the large triangle surrounding D, bounded by the edges y = -x + 6, y = x - 4 and y = 5.5) and C at the top. The former vertex (5; 3.25) shown as a greyed-out, crossed-out point inside the cell of D, labelled “disappears”. Point P(3, 5) marked with a cross in the cell of D.]

In the exam: in a problem about adding a site, marks are awarded for each perpendicular bisector that is correctly set up (midpoint, perpendicular gradient), for the intersection of the lines, and for checking that the vertex is equidistant from three sites with no other site closer. Always check the distances, and do not trust a point just because it is the intersection of two lines.