# 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 with points closer to that site than any other site.

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

## Construction

The line segments which separate 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,
\require{AMSsymbols} \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 $\require{AMSsymbols} \color{green}{y = x+1}$,

Remove all unnecessary lines but edges.

## Mastering Probability: Venn Diagrams Made Easy

Visualising multiple events using Venn diagrams to find probabilities is done quite often. Welcome to this comprehensive guide on mastering probability using Venn Diagrams. Whether…

## Mastering Integration by Parts: The Ultimate Guide

Welcome to the ultimate guide on mastering integration by parts. If you’re a student of calculus, you’ve likely encountered integration problems that seem insurmountable. That’s…

## Induction Made Simple: The Ultimate Guide

“Induction Made Simple: The Ultimate Guide” is your gateway to mastering the art of mathematical induction, demystifying a powerful tool in mathematics. This ultimate guide…

## High School Math for Life: Making Sense of Earnings

Salary Salary refers to the fixed amount of money that an employer pays an employee at regular intervals, typically on a monthly or biweekly basis,…

## Shifting and Scaling Effects on Mean and Standard Deviation

In this post, we will explain the effects of shifting (addition or subtraction) and scaling (multiplication or division) of scores in the entire data set.…