Voronoi Diagrams & Nearest Neighbor

3.3A

What is a Voronoi Diagram?

A Voronoi diagram partitions a 2D plane containing a set of points called sites ($S_1, S_2, \dots, S_n$) into convex regions called cells.
For every point $P$ strictly inside cell $V(S_i)$, the distance from $P$ to site $S_i$ is strictly less than the distance to any other site: $$d(P, S_i) < d(P, S_j) \quad \forall j \ne i$$
Edges (Boundaries): The segments, rays or lines separating two neighboring cells are parts of the perpendicular bisector of the two corresponding sites. Points on an edge are equidistant to both sites.
Vertices: Points where three (or more) edges meet. A Voronoi vertex is equidistant to the three nearest sites.

3.3B

To find the boundary line separating site $A(x_1, y_1)$ and site $B(x_2, y_2)$:
1. Find the midpoint $M$: $$M = \left( \frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2} \right)$$
2. Find the gradient of segment $AB$ ($m_{AB}$): $$m_{AB} = \frac{y_2 - y_1}{x_2 - x_1}$$
3. Find the perpendicular gradient $m_{\perp}$: $$m_{\perp} = -\frac{1}{m_{AB}}$$
4. Write the line equation passing through $M$: $$y - y_M = m_{\perp}(x - x_M)$$

Two medical clinics are located at $A(2, 5)$ and $B(8, 1)$. Find the Cartesian equation of the boundary separating their service zones.

Step 1: Midpoint $M$: $$M = \left(\frac{2 + 8}{2}, \frac{5 + 1}{2}\right) = (5, 3)$$

Step 2: Gradient $m_{AB}$: $$m_{AB} = \frac{1 - 5}{8 - 2} = \frac{-4}{6} = -\frac{2}{3}$$

Step 3: Perpendicular gradient $m_{\perp}$: $$m_{\perp} = -\frac{1}{-2/3} = \frac{3}{2}$$

Step 4: Equation through $(5, 3)$: $$y - 3 = \frac{3}{2}(x - 5) \implies 2(y - 3) = 3(x - 5) \implies 2y - 6 = 3x - 15 \implies 3x - 2y - 9 = 0$$

Final Answer: $y = \frac{3}{2}x - \frac{9}{2}$ (or $3x - 2y - 9 = 0$)

3.3C

When estimating an unknown property (e.g., rainfall, air quality index, soil pH) at an unmeasured location $P(x, y)$:
1. Determine which Voronoi cell contains point $P$.
2. Assign the measured value of that cell's generating site directly to $P$.
If $P$ lies closer to site $A$ than site $B$, the value at $P$ is estimated as the value at $A$.

Closed cell: $V(A)=\{P:d(P,A)\le d(P,S_j)\text{ for every }j\}$. Strict inequality describes its interior; boundary points can belong to several closed cells.
Gradient-free bisector: expand $d(P,A)^2=d(P,B)^2$ to obtain $2(x_B-x_A)x+2(y_B-y_A)y=x_B^2+y_B^2-x_A^2-y_A^2$. This handles horizontal and vertical site pairs.
Keep the correct half-plane: substitute the generating site into each distance inequality. Intersect these half-planes, then clip the cell to the specified territory.
Do not keep every bisector: a point on the AB bisector is an AB boundary point only if no third site is closer. Edges can be segments, rays or full lines.
Worked construction: A(0,0), B(4,0), C(0,4) give A’s cell $x\le2$, $y\le2$. AB’s edge is $x=2,y\le2$; AC’s edge is $y=2,x\le2$; BC’s edge is $x+y=4,x\ge2$. They meet at (2,2).

In the territory 0 ≤ x ≤ 6, 0 ≤ y ≤ 4, the shared boundary is x = 3.

A vertex may have four or more equally near sites. Three collinear distinct sites have parallel bisectors and no finite three-site vertex. Coincident sites need a shared-cell convention rather than a unique separating line.
Adding a site takes points from existing cells wherever the new site is closer. Recheck the inequalities; old boundaries may disappear.
Worked estimate: stations A(0,0), B(4,0), C(0,4) record 12, 20 and 30 mm. At P(3,1), squared distances are 10, 2 and 18, so estimate 20 mm from B.
On a tied boundary, state a tie rule or report both possible station values. Averaging is an additional modelling choice, not automatically nearest-neighbour interpolation.
Use coordinates on equal spatial scales. Euclidean distance assumes straight travel and equal accessibility; roads, rivers, terrain and station reliability can change the useful service zones.
Nearest-neighbour estimates are constant within each cell and can jump at boundaries. More stations may improve spatial resolution but do not guarantee unbiased measurements.