Coordinate Geometry, Perpendicular Bisectors, and Voronoi Diagrams

Where should a new hospital go so that every town is served by its nearest facility? Where is it safe to dump toxic waste, as far as possible from any well? These "nearest-neighbor" questions are answered elegantly by Voronoi diagrams, built from the coordinate geometry of perpendicular bisectors.

Coordinate geometry foundations

Given two points $A(x_1, y_1)$ and $B(x_2, y_2)$: - distance $AB = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$; - midpoint $M = \left(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2}\right)$; - gradient $m = \frac{y_2 - y_1}{x_2 - x_1}$.

Two lines are perpendicular when the product of their gradients is $-1$, i.e. $m_1 m_2 = -1$. This single fact powers the whole lesson.

Perpendicular bisectors

The perpendicular bisector of segment $AB$ is the set of all points equidistant from