UoL CS Notes
Menu

Voronoi Diagrams

COMP324 Lectures

Given a collection of $n$ points in space, its Voronoi diagram is a way of diving space in to $n$ convex regions, or Voronoi cells.

We generally have the following distances to work with:

  • Euclidean:

    \[\text{dist}_2(X,Y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2}\]

  • Manhattan:

    \[\text{dist}_1(X,Y)=\mid x_1-y_1\mid +\mid x_2-y_2\mid\]

  • Maximum:

    \[\text{dist}_{\infty}(X,Y)=\max(\mid x_1-y_1\mid,\mid x_2-y_2\mid)\]

Pen & Paper Method

PaperAndPencilVoronoi($P_1,\ldots,P_n$)

for each i in {1, ..., n} do
	define cell(P_i) by intersecting the n - 1 bisector
	half-places h_i(P_j)
end for

This method is tedious to draw by hand. There are alternative methods that can be computed.

Delaunay Triangulations

  1. Connect the points on the convex hell in a cycle.

  2. Iteratively remove any cycle of length at least four inside the convex hull by adding arbitrary lines connecting pairs of vertices.

    Leave the convex hull untouched and keep it planar.

  3. A pair of triangles sharing an edge is bad if the sum of the angles $\alpha$ and $\gamma$ is larger than 180 degrees.

    Remove all the bad pairs of triangles by replacing the diagonal $BD$ by $AC$.

Approximate

  1. Given the $n$ sites $S_1,\ldots,S_n$, in a rectangular region $R$, repeatedly sample points $P$ in $R$.
  2. Compute the distances $\text{dist}(P,S_i)$ and assign $P$ to the cell of minimum distance.

We can also complete the same thing using the following simpler algorithm:

  1. Superimpose a grid on $R$.
  2. Let $P$ denotes the centre of an arbitrary grid square.
  3. Assign $P$ to the cell of minimum distance.