# Voronoi Diagrams

## Introduction

This diagram shows the locations of the three hospitals, $A$, $B$ and $C$ in a city.

When a car accident occurs, it is important to locate the nearest hospital.

How could we improve the diagram to make it easier to identify the closest hospital to any given location?

If it is decided that a new hospital should be built as close as possible which is furthest from all three existing hospitals, where should a new hospital be built?

To solve these issues, we can construct a Voronoi diagram to determine the best solutions.

Consider the diagram here, for each hospital, there is a region which contains all the points that are closer to that hospital than to any other hospital.

Notice each region contains one hospital.

For instance, the point $K$ lies in the region containing hospital $A$, so hospital $A$ is the closest one to $K$.

In this case, the point $K$ lies in the region containing hospital $B$, so hospital $B$ is the closest one to $K$.

Now, the point $K$ lies in the region containing hospital $C$, so hospital $C$ is the closest one to $K$.

Point $K$ is equally close to hospital $A$ and $B$.

Point $K$ is equally close to hospital $A, B$ and $C$.

## Terminology

Significant points are called sites.

This diagram illustrates site $A$, site $B$ and site $C$.

Each site is surrounded by a region or cell which contains the points which are closer to that site than to any other site.

This diagram illustrates region $A$ or cell $A$.

## Construction

The line segments which separates the regions or cells are called edges.

The point(s) at which the edges meet are called vertex or vertices.

All points on the perpendicular bisector are equidistant from point $A(-5,2)$ and point $B(5,4)$.

The midpoint of $AB$ is $\displaystyle \left( \frac{-5+5}{2}, \frac{2+4}{2} \right) = \left( 0,3 \right)$

The gradient of $AB$ is $\displaystyle \frac{4-2}{5+5} = \frac{1}{5}$.

Thus, the gradient of the perpendicular bisector is
\begin{align} \displaystyle \frac{1}{5} \times m &= -1 \\ \therefore m &= -5 \end{align}.

So, the perpendicular bisector of $AB$ has gradient $-5$ and passes through $(0,3)$.

The equation of the perpendicular bisector of $AB$ is,
\begin{align} y – y_1 &= m(x-x_1) \\ y – 3 &= -5(x-0) \\ \color{red}{\therefore y} &\color{red}{= -5x + 3} \end{align}

Similarly, the equation of the perpendicular bisector of $BC$ is $\displaystyle \color{blue}{y= – \frac{1}{2}x + \frac{3}{2}}$,
and the equation of the perpendicular bisector of $AC$ is $\color{green}{y = x+ 1}$,

Remove all unnecessary lines but edges. 