WARNING: Even though the paperwork portion of the assignment may seem fairly small, it will likely take a considerable amount of time to understand the algorithm well enough to complete that work. Do not leave this assignment to the last minute!

Overview

In this assignment, you will learn about Voronoi diagrams, motivations for their use, and a divide and conquer algorithm to construct them. You will then apply this algorithm on paper and submit the work from each step.

An Application Scenario

Consider the following scenario. A school district with a fixed number of schools at various locations around the city wants to assign students to attend the school that is closest to their home. (They might want to do this, for example, to reduce the costs of busing all the students.) Rather than asking each student to determine the closest school themselves — say, by measuring the distance to all the nearby schools on the map — the school district wants to give them a simple picture that shows, at each place on the map, which of the schools is closest. That is called a Voronoi diagram.

Voronoi Diagrams

Figure 1, below, is a Voronoi diagram. It consists of specially marked points on the plane, called sites, and a collection of line segments, called edges, that divide the plane up into regions, each containing a single site. Furthermore, to be a Voronoi diagram, the region containing a particular site must have the property that every point inside that region is closer to that site than to any other site.

In our scenario above, the sites correspond to schools, and each student is assigned to the school that is in the region of the Voronoi diagram that contains their home. As described above, each region contains exactly one school (site), so each student is assigned to one school according to where they live.

Figure 1

Your Task

Your task is to compute the Voronoi diagram for the sites generated on this page (link) using the divide and conquer algorithm described below. To get your sites, enter your UW netid into the text box on the page and click the "Draw Points" button. (Your sites will be different from those of every other student, but everyone will be given exactly 12 sites.)

Once you complete the construction of your Voronoi diagram, you can check that it is (roughly) correct by visiting the page again. This time, after typing in your UW netid, click the "Draw Voronoi" button to see what the edges in your Voronoi diagram should should look like. Note that your diagram does not need to match the answer down to the pixel. Your goal should be to demonstrate your understanding of the algorithm rather than your ability with a ruler.

Your solution will also include a number of markings used in the construction process described below that are not shown on the web site: segments connecting sites whose bisectors make up the boundary, numbers to indicate the order in which they are used, and arrows to indicate the direction in which bisectors are extended. (See below for details.)

Computing Voronoi Diagrams

The following divide and conquer algorithm is used to compute Voronoi diagrams in O(n log n) time, as discussed in class.

Start by printing out the page with the your sites and copying the sites to a new sheet of paper. Then, apply the following process recursively:

1. Split the sites in half with a vertical or horizontal line.
2. Copy each half of the sites to a separate sheet of paper.
3. Recursively solve each problem — i.e., compute Voronoi diagrams for the sites on those pieces of paper.
4. Copy the Voronoi diagrams for the two halves back onto the original sheet in pencil.
5. Merge the two diagrams into one as described below.

You can stop recursing when you have only three sites. In that case, you can construct the Voronoi diagram directly using the approach described next.

Base case

The base case of this algorithm is when there are three sites in the subproblem. We will handle these differently depending on whether or not the sites are nearly in a line (colinear), as in the left-most picture of Figure 2 below. If they look more like the middle or right picture, then follow the directions for non-colinear sites. (If you are not sure whether they are colinear or not, just make a guess. The steps below will tell you whether you guessed right. If not, you can just try again using the other instructions.)

Click on any image to open a full size version in a new tab.

   

Figure 2

(These images are three of the four base cases from the example in Figure 1.)

Nearly Colinear Sites

Rotate the paper so that the three sites lie in a (roughly) vertical line. Now, draw a perpendicular bisector, as described in the next paragraph, between the top and middle sites and between the middle and bottom sites. These two bisectors should not intersect on the page. (If they do, switch to the directions for non-colinear sites instead.)

To draw a perpendicular bisector, draw a faint line connecting the two sites. Next, use a ruler to measure half-way between the sites. Then, line up the ruler so that it is perpendicular to the line connecting the sites, with its edge touching the mid-way point you just measured. Now, draw a line along the edge of the ruler. This line, which is perpendicular to and bisecting the line connecting the sites, traces out those points that are equal distance between the two sites. Finally, erase the line connecting the two sites, leaving only the perpendicular bisector.

Non-Colinear Points

Draw perpendicular bisectors between any two pairs of sites, as described in the prior paragraph. Let's call the sites in first pair A and B and the sites in the second pair B and C. (One site, B, must have been used twice.) The two perpendicular bisectors should intersect somewhere on the page. (If they do not, switch to the instructions for nearly colinear sites instead.)

The points along the perpendicular bisectors are equal distance between the two bisected sites. This means that the point where the two perpendicular bisectors intersect is both equal distance between A and B and also equal distance between B and C. Thus, it is, in fact, the same distance from all three sites.

Now, draw a segment connecting the third pair of sites, A and C, and measure the mid-way point. Then, line up the ruler so that it is touching both the mid-way point of the new segment and the intersection point of the first two perpendicular bisectors. We know that the perpendicular bisector of A and C must go through both of these points because the perpendicular bisector is the set of points that are the same distance between A and C and the intersection point is also the same distance from A and C. Thus, the edge of the ruler is now lined up along the perpendicular bisector of A and C.

Rather than drawing the entire perpendicular bisector of A and C, however, you can simply draw the ray starting from the intersection point and moving in the direction away from site B. All the points along this ray are the same distance from A and C but they are further away from B. Points just to the side of this ray are either closer to A than any other site or closer to C than any other site. In other words, this ray is the Voronoi edge that separates the region containing site A and the region containing site C.

The last step is to erase the parts of the first two bisectors that are not Voronoi edges. For the bisector of A and B, the ray starting from the intersection point and moving away from site C is a Voronoi edge by the argument above, so you can erase the ray from the intersection point moving toward C. Likewise, you can erase the portion of the bisector of B and C along the ray from the intersection point moving toward A.

(In principle, the procedure just described also works for colinear sites. The only problem in that case is that the intersection of the three bisectors is off the page. Rather than worry about the intersection point in that case, it is easier to simply bisect the two pairs of sites that are closer to each other, as we did in our earlier instructions, because those are the only two bisectors that appear as Voronoi edges on the page.)

Merge Step

After copying the Voronoi diagrams for the two halves of the sites back onto the page, we must merge them together into a single Voronoi diagram for all of the sites. The key insight of this algorithm is that all the Voronoi edges separating sites on the same half are already included at this point. The only missing edges are those separating regions closest to a left half site from regions closest to a right half site. As we will see, the missing edges connect together into a piece-wise linear path that separates the plane based on which of the two sides is closest.

Following figure shows some examples of what the results of the merge will look like. The piece-wise linear separating path is drawn in green. Click on any image to open a full size version in a new tab.

   

Figure 3

(The left diagram is the merge of the first two diagrams in Figure 2.
The middle diagram is the merge of the last diagram in Figure 2 with another one (not shown).
The right diagram is the merge of the previous two diagrams.)

These instructions will assume that you split the sites in half with a vertical line. If you used a horizontal line, just rotate the page 90 degrees so the dividing line is now vertical.

Start by finding the site from the left that is at the top and (if there are multiple sites near the top) closest to the dividing line. Call this site P₁. Likewise, find the site on the right that is top-most and (if there are multiple near the top) closest to the dividing line. Call this site Q₁.

Next, bisect sites P₁ and Q₁ and find out where their perpendicular bisector meets the top of the page. Below, we will start drawing their bisector from that point. When finding this perpendicular bisector and the ones we need below, follow the instructions above, but, this time, do not erase the line segment between the two sites. Instead, leave the line segment between the sites drawn with a dashed line and label it "1" to indicate that these are the first two sites bisected.

At this point, it is worth checking with your ruler that P₁ and Q₁ are actually the closest two sites from each half to the point just identified at the top of the page. If you find that a different site from the right half, say, is closer, then start over using that site as Q₁ instead. (Likewise, if a point from the left half is closer than P₁, then start over using that site in place of P₁.) Don't continue until you have a P₁ and Q₁ that are closest to the point where their perpendicular bisector meets the top of the page.

Continue by repeating the steps described below until they indicate to stop. At the start of each iteration, we are keeping track of two sites — one from the left side, P_i, and one from the right side, Q_j — along with the point at which we will start drawing their bisector and the direction in which we will start drawing. (On the first iteration, these are P₁, Q₁, and the point where their bisector meets the top of the page, from which we will start drawing downward.) We will maintain the invariant that P_i is the closest site from the left side and Q_j is the closest site from the right side along the Voronoi edge that we are about to draw.

1. Draw the perpendicular bisector between P_i and Q_j starting from the starting point and moving in the starting direction. Continue drawing until this line segment hits an edge from one of the two Voronoi digrams copied onto the page or until it goes off the bottom page, whichever comes first. Also draw a small arrow next to the line segment just drawn indicating the direction in which you drew it.

2. If the line segment you drew continues to the bottom of the page, then you are done.

3. Otherwise, the perpendicular bisector has hit a Voroni edge. We will suppose that it was an edge from the Voronoi diagram for the right half of the sites. The other case is analogous and is discussed more below.

   Since we were previously drawing in the region closest to Q_j, we must have hit an edge separating points that are closest, amongst all sites on the right half, to Q_j from those closest to some other site on the right half. Let's call this new site Q_j+1.

   Recall that the missing edges in the diagram are those separating the closest site on the left from the closest site on the right. Since Q_j is no longer the closest site on the right after the intersection with the edge between Q_j and Q_j+1, this is the end of the Voronoi edge that separates P_i from Q_j.

4. Erase the part of the Voroni edge between Q_j and Q_j+1 that goes past the intersection point above. The points along that edge past the intersection point are closer to P_i than to either site from the right side, so they are not an edge of the merged Voronoi diagram. (The Voronoi edges are points that are equal distance between the two closest sites. Since those you are erasing are closer to P_i than to any other site, they cannot be an on edge of this Voronoi diagram.)

5. On the next iteration, our site from the right half will be Q_j+1 rather than Q_j. Draw a dashed line segment between P_i and Q_j+1, and number it one larger than the previous dashed line segment.

   Find the mid-way point along the dashed segment. The perpendicular bisector between P_i and Q_j+1 goes through this point and the intersection point from step 3 above. Our starting point for drawing the bisector in the next iteration will be the intersection point, and we will draw toward the line segment that connects the two points.

In the case where the perpendicular bisector between P_i and Q_j hits a Voronoi edge from the diagram for the left half sites, you will end up advancing from P_i to P_i+1 rather than from Q_j to Q_j+1. That is, you will continue with Q_j in the next iteration but not with P_i.

Finally, there is one especially tricky case: it is possible that the perpendicular bisector hits an edge from both of the two Voronoi diagrams at exactly the same point. In that case, the intersection point is equal distance between four sites: P_i and P_i+1 from the left half and Q_j and Q_j+1 from the right half. You handle that case by advancing to P_i+1 and Q_j+1 in the next iteration. Once again, the intersection point will be the starting point for drawing their bisector, and you will in the direction toward the numbered line segment connecting them. (Note that you will need to erase parts of both of the intersected Voronoi edges.)

When you reach the bottom of the page, make the separating path you have constructed stand out by drawing over it with a color not used anywhere else on the page. (We used green in the figures above. All the other markings where grey, from a pencil.)

Why Submit 7 pages?

• 1 page containing all 12 sites with the completed Voronoi diagram for the whole problem
• 2 pages each containing 6 sites with the completed Voronoi diagrams of the first split
• 4 pages each containing the completed Voronoi diagram of one of the four base cases of 3 sites

Advice

Please try to understand the guiding example Voronoi diagram construction given in the figures above before attempting your own.

Please do this with pencil and a ruler. It sounds like dumb advice, but it's almost guaranteed to give headaches if you try it with pen or try approximating the straight lines.

The merge step is very tricky to do correctly without messing up, so please be very careful and take your time with it.

I highly recommend doing the simulation from scratch again once you've done it once. It's very easy to make a mistake the first time when you're trying to understand the algorithm.