2017 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 9
Problem
Consider a triangulation (mesh) of a polygonal domain like the one in the figure below. (a) Given the vertices of a triangle, devise a strategy for determining if a given point is inside that triangle. (b) Will your strategy work for polygons with more than three sides? (c) After implementing your strategy in an optimally efficient computer code you find that the search for a problem with triangles, on average, takes seconds. You refine the triangulation by subdividing each of the triangles into smaller triangles by placing a new vertex at the center of gravity of each triangle. On average, how long will it take to find a point in the new mesh?
Solution
See also
2017 UNM-PNM Contest II (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 | ||
All UNM-PNM Problems and Solutions |