Voronoi diagrams help us find the closest points from an arbitrary point. Let’s start by displaying a set of points on a plane.

The Voronoi diagram draws boundaries between each of those points. Around each point, regions will develop called the Voronoi regions. Let’s see how we would draw those boundaries. Each boundary should be in the middle of two points. Let’s begin by drawing a boundary between point 1 and point 2.

The boundary should be directly in the middle separating the two points. Let’s move to creating a boundary between points 2 and 3.

Wherever the points intersect, we’ll remove that line segment.

We’ll create the boundary between point 2 and 6 next.

We also have to create a boundary between point 1 and point 6. This will require trimming on a couple of different borders.

The final product looks like the following.

Let’s move on and create a border between 2 and 7.

Next, we’ll create a border between points 6 and 7.

Next, we’ll create a border between points 6 and 8.

Next, we’ll create a border between points 7 and 8.

Next, we’ll create a border between points 5 and 7.

Next, we’ll create a border between points 7 and 9.

Let’s draw a border between points 5 and 9.

A couple of more points to go. We’ll draw the boundary for points 3 and 5 next.

Next, we’ll create a border between points 3 and 4.

We’ll draw a boundary between points 4 and 5.

From the looks of the diagram, there are a couple of boundaries that were not accounted for, the boundary between point 1 and 3 and the boundary between point 8 and 9. Let’s quickly adjust those and complete the Voronoi diagram.

Once we have the regions defined, we can draw the lines that make up the Delaunay triangulation. The simple rule of thumb is, if the points share a border, draw a line connecting them. Point 1 shares a boundary with points 2, 3, and 6, so we’ll draw lines connecting those points.

Although it may look like the line crosses two boundary lines when going from point 1 to 3, we can quickly modify that line to show where it will cross the border only once.

Point 2 shares boundaries with unconnected points 3, 6, and 7; it’s already connected to point 1.

Point 3 shares boundaries with unconnected points 4, 5, and 7.

Point 4 shares a boundary with the unconnected point 5.

Point 5 shares boundaries with unconnected points 7 and 9.

Point 6 shares boundaries with unconnected points 7 and 8.

Point 7 shares boundaries with unconnected points 8 and 9.

Point 8 shares a boundary with the unconnected point 9.

Point 9 is already connected to all other points that share its boundary, so this completes the construction of the Delaunay triangles. If we knew the weight of each edge, we could construct a minimum spanning tree after the creation of the Delaunay triangles.

How would we find the Voronoi diagram for a set of points in a rectilinear metric? Let’s start with a small set of points on a grid.

The distance from p1 to p2 is 4 units regardless of the path that you take.

The middle point going through either route is 2 units away.

We’ll start by drawing a line connecting those two points.

To separate the points equally, we’ll draw lines protruding from each endpoint that maximizes the area of each point.

Next, we’ll examine the boundary for points 1 and 3. This will create a border similar to the one separating points 1 and 2. Again, regardless of the path that you take, to get to the midpoint between those two points, it will require 2 units of travel.

We’ll connect those two points and we’ll shift the bottom vertical line.

Next, we must draw a boundary between points 2 and 3. The midpoint is 1 unit away, so a horizontal line will be drawn separating those two points.

A border needs to be constructed between points 2 and 4. The distance to point 4 from point 2 is 6 units. The midpoint of the trajectory is 3 units from points 2 and 4.

We will draw a line connecting those two points and we’ll draw vertical lines from the endpoints.

There is still the boundary between points 3 and 4 that needs to be constructed. Since the distance between points 3 and 4 is the same as the distance between points 2 and 4, a similar approach is taken to construct the boundary between them. The midpoint is 3 units away, so we’ll draw a line that connects the midpoints from the top and from the bottom. The right-bottom, vertical line will be moved to the new endpoint.

We can again construct the Delaunay triangles by connecting the points that share a boundary. Point 1 shares boundaries with points 2 and 3.

Point 2 shares boundaries with unconnected points 3 and 4.

Point 3 shares a boundary with the unconnected point 4.

All points are now connected to their immediate neighbors. This completes the Delaunay triangulation. Since we know the distance to each point, we can construct a minimum spanning tree. There are a couple of variations of the minimum spanning tree for this problem, but we’ll choose one. The total length of this MST is 12.

If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.