Voronoi Diagrams

Introduction

Voronoi Diagrams-01

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.

Absolute Value Algebra Arithmetic Mean Arithmetic Sequence Binomial Expansion Binomial Theorem Chain Rule Circle Geometry Common Difference Common Ratio Compound Interest Cyclic Quadrilateral Differentiation Discriminant Double-Angle Formula Equation Exponent Exponential Function Factorials Functions Geometric Mean Geometric Sequence Geometric Series Inequality Integration Integration by Parts Kinematics Logarithm Logarithmic Functions Mathematical Induction Polynomial Probability Product Rule Proof Quadratic Quotient Rule Rational Functions Sequence Sketching Graphs Surds Transformation Trigonometric Functions Trigonometric Properties VCE Mathematics Volume

 



Your email address will not be published. Required fields are marked *