In this assignment, you examine a practical procedure used in computer-aided design and computational fluid dynamics. You will make some assessments regarding this procedure.
The word triangulation has two definitions. The first, and most common, is the use of trigonometry to establish the position of an object relative to two or more fixed, known locations. This is common in navigation. The second definition is the decomposition of a polygon into triangles. This provides a convenient representation of a polygon that may be used in a variety of computational contexts, such as those mentioned above. You will not be concerned about computer science; rather, you study the variety of ways in which polygons may be triangulated.
For the first three questions, regard the polygons as convex. If you select any pair of points inside or on the boundary of the polygon, and join them with a line segment, that line segment will remain inside or on the boundary of the polygon; it will never cross the boundary and be outside the polygon. The final question asks you to consider what sort of effect the loosening of this restriction might have on your efforts.
Below is a series of diagrams showing the ways in which the first few polygons may be triangulated. At the start of this task, regard the vertices of the polygon as distinct; that is, they are distinguished from one another, perhaps by a label, letter, or number. The possible triangulations T(n) of an n-gon, for n = 3, 4, and 5, are illustrated here:
T(3) = 1 (a triangle is its own triangulation!)
T(4) = 2 (a convex quadrilateral can be triangulated diagonally on each of two diagonals)
T(5) = 5 (a pentagon can be triangulated with two segments joining each vertex to its two opposite vertices)
A: Determine T(n) for n = 6, 7, & 8.
B: Do you detect a pattern to these numbers? This pattern may arise out of the numbers or the manner in which you generated triangulations. A closed-form function for T(n) is relatively straightforward, but is fairly nontrivial to construct; we will not explore this here.
C: How would T(n) change if we ignore the vertices’ distinctness? That is, if we remove the labels, and say two triangulations are identical if one may be transformed into the other via a rotation or a reflection, how does this change T(n) for n = 4, 5, 6, 7, & 8?
D: What effect does relaxing the convexity restriction have on T(n)? See how T(n) changes for n = 4, 5, & 6. Do you see a pattern?
The word triangulation has two definitions. The first, and most common, is the use of trigonometry to establish the position of an object relative to two or more fixed, known locations. This is common in navigation. The second definition is the decomposition of a polygon into triangles. This provides a convenient representation of a polygon that may be used in a variety of computational contexts, such as those mentioned above. You will not be concerned about computer science; rather, you study the variety of ways in which polygons may be triangulated.
For the first three questions, regard the polygons as convex. If you select any pair of points inside or on the boundary of the polygon, and join them with a line segment, that line segment will remain inside or on the boundary of the polygon; it will never cross the boundary and be outside the polygon. The final question asks you to consider what sort of effect the loosening of this restriction might have on your efforts.
Below is a series of diagrams showing the ways in which the first few polygons may be triangulated. At the start of this task, regard the vertices of the polygon as distinct; that is, they are distinguished from one another, perhaps by a label, letter, or number. The possible triangulations T(n) of an n-gon, for n = 3, 4, and 5, are illustrated here:
T(3) = 1 (a triangle is its own triangulation!)
T(4) = 2 (a convex quadrilateral can be triangulated diagonally on each of two diagonals)
T(5) = 5 (a pentagon can be triangulated with two segments joining each vertex to its two opposite vertices)
A: Determine T(n) for n = 6, 7, & 8.
B: Do you detect a pattern to these numbers? This pattern may arise out of the numbers or the manner in which you generated triangulations. A closed-form function for T(n) is relatively straightforward, but is fairly nontrivial to construct; we will not explore this here.
C: How would T(n) change if we ignore the vertices’ distinctness? That is, if we remove the labels, and say two triangulations are identical if one may be transformed into the other via a rotation or a reflection, how does this change T(n) for n = 4, 5, 6, 7, & 8?
D: What effect does relaxing the convexity restriction have on T(n)? See how T(n) changes for n = 4, 5, & 6. Do you see a pattern?