Voronoi diagrams and applications

The following regions contain two and three sites respectively. Construct the Voronoi diagrams by writing down on each edge the equation of the corresponding line.

(a)

[2]

(b)

[3]

The following region contains three sites, $A(2,5)$, $B(2,1)$ and $C(8,1)$.

(a) Write down the equation of the perpendicular bisector

(i) of the line segment $[AB]$,

(ii) of the line segment $[BC]$.[2]

(b) Find the equation of the perpendicular bisector of the line segment $[AC]$.[4]

(c) Hence construct the Voronoi diagram for the region above; indicate the coordinates of the vertex.[3]

The Voronoi diagram for three cells, $A(4,5)$, $B(2,1)$ and $C(8,1)$ is shown below.

(a) Write down the equation of the edge between B and C.[1]

(b) Find the equation of the edge between A and B in the form $ax+by+d=0$, where $a,b,d\in\mathbb{Z}$.[4]

(c) Write down the coordinates of the only one vertex.[1]

(d) Given that the edge between A and C has equation $y=x+c$, find the value of $c$.[2]

The Voronoi diagram for four sites, $A(4,6)$, $B(3,1)$, $C(6,2)$ and $D(4,2)$, is shown below.

(a) Find the equation of the edge $L_3$ between cells A and C in the form $y=mx+c$.[4]

(b) Complete the table of the edges below.

Line	Equation
$L_3$
$L_1$	$y=-0.2x+4.2$
	$y=-x+5$
	$y=-3x+15$
	` $y=4$
$L_6$

[4]

The diagram shows five sites are represented by the points $O(0,0)$, $A(2,2)$, $B(2,-2)$, $C(-2,-2)$ and $D(-2,2)$.

(a) On the same diagram, complete the Voronoi diagram for the five sites.[3]

The border of cell O contains four edges.

(b) Write down the equations of the four edges.[3]

(c) Find the area of the cell O.[2]

The Voronoi diagram for four sites, $A(1,1)$, $B(1,5)$, $C(6,1)$ and $D(2,3)$, is shown below.

The vertex Z is the midpoint of the line segment $[AC]$.

(a) Write down the coordinates of the vertex Z.[1]

The equation of the edge $[XY]$ is $-2x+4y=13$.

(b) Find the equation of the edge $[ZY]$ in the form $ax+by=d$, where $a,b,d\in\mathbb{Z}$.[4]

(c) Hence, find the coordinates of the vertex Y.[2]

(d) Find the exact value of the length ZY.[2]

Consider now the cell XYZ. The length XY is $\frac{10\sqrt{5}}{3}$.

(e) Show that the edges $[XZ]$ and $[ZY]$ are perpendicular.[3]

(f) Let $\theta=\widehat{XYZ}$.

(i) Show that $\cos\theta=\frac{4}{5}$.

(ii) Explain why $\sin\theta=\frac{3}{5}$.[4]

(g) Find the exact value of the area of the triangle XYZ.[2]

Part of the Voronoi diagram for four sites, $A(1,1)$, $B(4,0)$, $C(4,4)$ and $D(8,2)$ is shown below. The two vertices of the Voronoi diagram are shown by the points X and Y.

(a) Two edges are missing.

(i) Draw the two edges.

(ii) Find their equations.[6]

(b) Write down the coordinates of the two vertices X and Y.[2]

(c) Find the exact value of the distance between the sites A and D.[2]

(d) Find the area of the quadrilateral ABCD.[4]