Overview

In this assignment, you will simulate the dynamic programming algorithm discussed in lecture for computing the value of the optimal triangulation of a convex polygon. You will then use the information produced to draw the optimal triangulation.

Background

Triangulations of Convex Polygons

Figure 1, below, shows a picture of a convex polygon (left) and a triangulation of that polygon (right). The triangulation represents the same polygon as a union of triangles with non-overlapping interiors. (Triangles can still touch along their edges, however.)

Figure 1

We will consider only triangulations, like the one shown here, that are produced by adding lines, called chords, between vertices of the polygon. Furthermore, we will not allow any two chords to cross.

Optimal Triangulations

Even subject to these restrictions, the number of possible triangulations grows exponentially with the number of vertices. The problem we are interested in is finding the triangulation that maximizes or minimizes some measure of the quality of the triangles in the triangulation.

Different quality measures are used in different applications. For example, when creating a triangulation for use in a finite element analysis, it is often preferred to have triangles that are as close to equilateral as possible. That quality can be measured (approximately) by dividing the area of the triangle by the sums of the squared lengths of its sides. Smaller numbers are worse, so we want to find the triangulation for which the minimum value of this quantity over all triangles (i.e., the quality of the worst triangle) is as large as possible.

For this assignment, we will instead use a quality measure chosen for a different reason, namely, to be easy to calculate by hand. In particular, we will define the quality of a triangle to be the maximum length of any of its sides. We want this to be as small as possible. Likewise, for the full triangulation, our metric will be the maximum length of any side of any triangle, and our goal will be to find the triangulation such that the maximum edge length over all triangles is smallest.

Your Task

Your task is to calculate the optimal triangulation for the convex polygon generated on this page (link) using the dynamic programming algorithm described below. To get your polygon, enter your UW netid into the text box on the page and click the "Draw Polygon" button. (Your polygon will be different from that of every other student, but everyone will be given a polygon with exactly 8 vertices.)

Once you complete the construction of your triangulation, you can check that it is correct by visiting the page again. This time, after typing in your UW netid, click the "Triangulate" button to see what chords you should have added to produce the optimal triangulation.

Part 1: Computing Distances Between Vertices

Since our measure of the quality of a triangle uses the lengths of the sides, we will start by calculating all of those. We do not yet know which triangles we will use; however, as discussed above, we will only consider triangulations produced by simply adding chords between the vertices of the polygon. Hence, the length of the sides of any triangle will always be the distance between two vertices of the polygon, so it will be sufficient to calculate the distances between each pair of vertices. Our task in Part 1 is to perform those calculations.

Rather than doing these calculations with paper and pencil, it will be easiest to perform them in Excel or Google Spreadsheets. Start by copying the X and Y coordinates shown on the page next to your polygon and pasting them into a new spreadsheet. Then, copy those same numbers into two rows along the top as shown here (you may need to type these in by hand):

Next, add the vertex numbers (1 to 8) next to their coordates, both horizontally and vertically. The result should look like this (in the picture, the vertex numbers are surrounded by a black border):

Now, we can fill in each entry of the table in the bottom-right with the distance between the vertex in that row and the vertex in that column. We will calculate the distance using the usual Euclidian distance formula. Here is what the formula should look like for the distance between vertex 1 (row) and vertex 1 (column):

Note the presence of the "$"s in this formula. Those indicate to Excel the parts of the formula that should not change when you drag or copy the formula to other cells. In this case, we are using the "$"s to ensure that it always gets the row vertex coordinates from columns A and B and that it always gets the column vertex coordinates from rows 1 and 2.

If we use this formula as is, most of the calculated distances will not be integers. To make your table easier to read, you can tell Excel to round all of the numbers to integers by adding a call to "ROUND(.., 0)" like this:

For this assignment, it should be sufficient round all of the numbers to integers since distances between different pairs of vertices are unlikely to differ by less than 1 pixel.

Finally, fill in the rest of the table by selecting cell D4 and then dragging small square in the bottom right corner of that cell to the right across all eight columns. When you do that, Excel should respond by copying the formula into all of the cells in the row, showing you distances from vertex 1 to every other vertex. Next, with all eight cells of the first row still selected, grab the same small square and drag it down across all eight rows. You should now see a table like this one, showing you the distances between each pair of vertices:

In addition to saving this worksheet to turn in later, you will also likely want to print out a copy to keep next to you as you work on part 2.

Part 2: Computing the Value of the Optimal Triangulation

With all the distance calculations ready for use, our task in Part 2 is to calculate the quality of the optimal triangulation. That is, we want to the quality of the optimal triangulation. In Part 3, we will use this to find the optimal triangulation.

Open a new spreadsheet. In this one, we will calculate the quality of the optimal triangulation of each range, i .. j, of at least three vertices. We will start with the smallest ranges, containing each just three vertices, and then work our way up through larger ranges until we eventually calculate the quality of the optimal triangulation of the full range 1 .. 8.

Base case

A range i .. j containing just three vertices is already a union of (just one) triangle, so we do not need to consider adding any more chords. However, we will still need to know the quality of each of these triangles.

Start by creating a row for each range containing exactly three vertices. Since we have eight total vertices, we get a row for the six ranges shown here:

We defined the quality of a triangle to be the maximum length of any of its sides, so we can calculate the quality of the triangles by finding the maximum distance between any of those three vertices.

Each of those distances is already recorded in the table we constructed in Part 1. For example, to calculate the quality of the triangle corresponding to the range 3 .. 5, we find the maximum of the lengths at the three cells shown in blue on this table:

For this example, the quality of the triangle is 391.

Perform that same calculation for each of the six ranges and record the results next to those ranges in the worksheet. (For each range, you will need to look at a different set of cells in the distance table, but you may notice a pattern in where to look as you work through different ranges.) When you are done, your worksheet should look like this, albeit with different numbers:

Recursion

Next, we will calculate the quality of the optimal triangulation of each range of four or more vertices, starting with those of length four and working up to the full set of eight vertices.

Start by labeling a row for each of these ranges. However, this time (unlike above), leave at least three blank rows between each range. We will need this extra space for our calculations.

For a range i..j, we need to calculate the quality of the optimal triangulation using each choice of the third vertex in the triangle containing the edge (i,j). As we discussed in lecture, every triangulation of i..j includes a triangle (i,k,j), for some k satisfying i < k < j, along with triangulations of the two subranges it creates: i..k and k..j.

For example, to triangulate the polygon over the vertices 1..8 shown in Figure 1, we could try creating a triangle (1,4,8). That would split polygon into two sub-ranges, 1..4 and 4..8, outlined in blue here:

Triangulating each of those recursively can lead to, for example, the following triangulation of the polygon:

In our worksheet, we will calculate the quality of the optimal triangulation for each choice of this k. The quality of the optimal triangulation of i..j is then the best of these.

We will work through how to perform the calculations for the range 2..6. The calculation for every other range can be performed similarly.

We will use the third and later in the worksheet to perform the calculations for each choice of the vertex making the triangle with 2 and 6 in the triangulation. In this case, the options are vertices 3, 4, and 5.

If you want, you can label the third and later columns 2 through 7, to indicate which columns will be used for the calculations with each choice of third vertex. For the range 2..6, we will need only columns 3, 4, and 5, but other ranges will need the other columns as well.

With those labels in place, my rows for the range 2..6 are arranged as shown here. (Ignore the two zeroes for now. I will explain those below.)

We will start by calculating the quality of the triangle containing the edge (2,6) for each choice of third vertex (3, 4, or 5). Perform each calculation just as we did in the base case, by finding the maximum distance between any of those three vertices. Place the answers in the middle row of the three blank ones, with each number in the column corresponding to the third vertex of that triangle. The result should look something like this:

In this example, the number below the top zero is the quality of the triangle (2,3,6), the number just to the right of it is the quality of the triangle (2,4,6), and the number to the right of that is the quality of the triangle (2,5,6).

In the row above the one we just completed, we will fill in the quality of the optimal triangulation of the first subrange of remaining vertices. That is, for a range i..j with k chosen as the third vertex in the triangle containing the edge (i,j), this is the subrange i..k.

In our example range 2..6, the first subrange is 2..3 when 3 is chosen as the third vertex, 2..4 when 4 is chosen as the third vertex, and 2..5 when 5 is chosen as the third vertex.

Each of these subranges is shortest than the current one, 2..6 (and in general, i..k is shorter than i..j since j < k), so we will have already calculated the quality of its optimal triangulation above in the worksheet. The lone exception to this is 2..3. We do not have a quality for this subrange because it cannot be triangulated: two vertices can only make an edge, not a triangle.

For each of the subranges other than 2..3, we can copy the quality of its optimal triangulation from above in the worksheet into this row. Record the quality for the subrange 2..k in the column for third vertex k. For the range 2..3, that is just an edge, write 0. The result should look like this:

Next, we do the same thing for the subranges of the form k..6, and record these in the row just below the two we just filled in. Record the quality of the optimal triangulation for the range k..6 in the column for third vertex k. For this row, the one exceptional case is 5..6, which is just an edge, so we write a 0 in the column labeled 5. The result should look like this:

In the row just below these, we will record the quality of the optimal triangulation with each choice of third vertex. This is simply the maximum (worst) of the qualities of the triangle made with the third vertex and the qualities of the optimal triangulations of the two subranges made by that choice of third vertex. For each choice of third vertex, those three numbers are recorded in the same column, so we simply calculate the maximum of those three in the next row down.

The optimal triangulation is the one resulting from whichever choice of third vertex gives the best quality. That is simply the minimum of the numbers we just calculated. Record this next to the label of the range:

Finally, indicate which one of the choices achieved the minimum, by putting a border around (or circling) it. In case of ties, choose the lower numbered vertex. The final result should look something like this:

In this case, the result indicates that the optimal triangulation of the range 2..6 starts by forming the triangle (2,4,6).

You can perform a similar calculation for each range in the worksheet, starting with the smaller ones and working up to 1..8. As noted above, we need the quality of the optimal triangulation from shorter ranges in order to complete the next range, so it is necessary to calculate them in this order.

The same process just described can be carried out for each of these ranges. The number of columns you will need to fill out will be two less than the number of vertices in the range. For example, since 2..6 contains five vertices, we filled out three columns above. Other than a change in which and hwo many columns need to be filled out, the calculations are done in the same manner.

Part 3: Finding the Optimal Triangulation

To check that your results are correct, you should draw the optimal triangulation.

To do so, first, print out a copy of your polygon from the web page. Next, look at the row of your worksheet for the range 1..8 and see which third vertex produced the optimal triangulation. Then, draw that triangle by connecting 1 and 8 to that vertex. Doing so will split the polygon into (up to) two pieces, as shown in blue in Figure 2, each of which corresponds to another range.

You can then apply this process recursively to each of those subranges: look each one up on the worksheet to find the third vertex in the optimal triangulation, draw that triangle, et cetera. You can stop the recursion when you get to ranges of size three (or smaller), as they are already triangulated.

When you are done, you should have a picture something like the right side of Figure 1, with polygon now decomposed into the union of triangles.

You do not need to turn in this drawing, but you should check that it matches the result you see on the page that gave you your polygon when you click the "Triangulate" button. If it does match, then your calculations are mostly correct.