# 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.

Algebra Algebraic Fractions Arc Binomial Expansion Capacity Common Difference Common Ratio Differentiation Double-Angle Formula Equation Exponent Exponential Function Factorise Functions Geometric Sequence Geometric Series Index Laws Inequality Integration Kinematics Length Conversion Logarithm Logarithmic Functions Mass Conversion Mathematical Induction Measurement Perfect Square Perimeter Prime Factorisation Probability Product Rule Proof Pythagoras Theorem Quadratic Quadratic Factorise Ratio Rational Functions Sequence Sketching Graphs Surds Time Transformation Trigonometric Functions Trigonometric Properties Volume

## Responses