Question 656226: 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 can be used in a variety of computational contexts, such as those mentioned above. For this assignment you will not be concerned about computer science; rather, you will study the variety of ways in which polygons may be triangulated.
For the first three questions, consider the polygons to be 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, consider 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.)
Questions
A. Determine T(n) for n = 6, 7, & 8. (Jessica)
In the case of a triangle, T(3) = (2)/(3-1)! = 2/2 = 1, which means that there is only one way to triangulate a triangle.
In the case of a quadrilateral, T(4) = (2*6)/(4-1)! = 12/6 = 2, which means that there are two ways to triangulate a quadrilateral.
In the case of a pentagon, T(5) = (2*6*10)/(5-1)! = 120/24 = 5, which means that there are 5 ways to triangulate a pentagon.
T(5) = 5 (A pentagon can be triangulated with two segments joining each vertex to its two opposite vertices.)
T (6) = (2*6*10*14)/(6-1)! = 1680/120 = 14, which means that there are 14 ways to triangulate a hexagon.
T (7) = (2*6*10*14*18/(7-1)!=30240/720=42, which means that there are 42 ways to triangulate a heptagon.
T (8) = (2*6*10*14*18*22)/(8-1)! =665,280/5040=132, which means that there are 132 ways to triangulate an octagon.
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; you will not have to explore that here.)
C. How would T(n) change if you ignored the vertices’ distinctness? That is, if you remove the labels, and say two triangulations are identical if one can 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 forn = 4, 5, & 6. Do you see a pattern
Answer by solver91311(24713)   (Show Source):
You can put this solution on YOUR website!
What ever gave you the idea that you could just drop your entire assignment in here and expect it to get done for you? Did you read the instructions for posting on this site?
John
My calculator said it, I believe it, that settles it
|
|
|
